Switch Regular Upward Planarity Testing
Question: An upward planar drawing of a planar digraph G is a crossing-free drawing Gamma of G such that all the edges are represented as curves monotonically increasing in the vertical direction. A switch angle in a face f of Gamma is an angle formed by two consecutive edges e1, e2 on the boundary of f such that e1 and e2 have opposite direction. Each switch angle in a face of Gamma can be labeled either S (if the associated geometric angle is smaller than 180 degrees) or L (if the associated geometric angle is larger than 180 degrees). An internal face f of Gamma is switch regular if walking clockwise on its boundary there is at most one maximal sub-sequence of S labels with length greater than one. The external face of Gamma is switch regular if there is no two consecutive S labels walking clockwise on its boundary. Drawing Gamma is switch regular if all its faces are switch regular. Let G be an embedded planar digraph; we ask whether there exists a polynomial-time algorithm that tests if G admits a switch regular upward planar drawing that preserves its embedding.[PDF file]
Members: Emilio Di Giacomo, Walter Didimo, Francesco Giordano, Maurizio Patrignani.
Results:
- Let G be a planar digraph with a given planar embedding, and let n be the number of vertices of G. If every face of G has at most 6 switch angles, then there exists an O(n2 log n)-time algorithm that tests if G admits a switch-regular upward planar drawing.
Open Questions:
- Are there any properties for the complete saturators of switch-regular upward planar drawings, which can lead to a characterization?
- If yes, can these properties used to design a polynomial-time algorithm for switch-regular upward planarity testing in the general case, or the problem for the general case is NP-hard?
Colored Simultaneous Geometric Embedding
Question: Let G1, ..., Gh be h > 1 outerplanar graphs having the same number n of vertices. Suppose that the vertices of each graph are colored using 1 < k < n distinct colors that we denote by the integer numbers 1, ..., k, and suppose that, for each color i, the number of vertices colored i is the same in G1, ..., Gh. We ask whether there exists a set S of n points such that:- Each Gi (i = 1, ..., h) admits a planar straight-line drawing with the vertices mapped to the points of S.
- For each point p in S, the vertices of G1, ..., Gh mapped to p have the same color.
[PDF file]
Members: Markus Geyer, Carsten Gutwenger, Seok-Hee Hong, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, Petra Mutzel, Antonios Symvonis.
Results:
- Any number of 3-colored paths admit a colored simultaneous embedding.
- There exist four 4-colored paths, which do not admit a colored simultaneous embedding (each color appears at least twice in each path, no "fixed" vertices).
- Let C be a 2-colored caterpillar and T be a 2-colored tree, C and T always admit a colored simultaneous embedding.
Open Questions:
- Admit 3 4-colored paths allways a colored simultaneous embedding?
- Admit 2 2-colored (k-colored) trees always a colored simultaneous embedding?
- Admit a 3-colored tree and a 3-colored path always a colored simultaneous embedding?
- Can you embedd any 2-colored outerplanar graph in such a way, that there exists a line (closed curve) seperating the different colors?
LMST drawability problem
Question: Let S be a set of points in the plane. The unit distance graph of S, denoted as U(S), is the graph obtained by connecting those points that have relative distance less than or equal to one. For a point u in S, denote by N(u) the set of points that are adjacent to u in U(S). Also, denote by MST(N(u)) the minimum spanning tree of the subgraph of U(S) induced by the points in N(u). A Local minimum spanning tree of U(S) is a specific proximity graph that can be defined in two different ways:- LMST(U(S))+ = {(u,v) in U(S): (u,v) belongs to MST(N(u)) or to MST(N(v))}
- LMST(U(S))- = {(u,v) in U(S): (u,v) belongs to MST(N(u)) and to MST(N(v))}
[PDF file]
Members: Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, Katharina Lehmann, Giuseppe Liotta, Ioannis Tollis, Franscesco Trotta, Sue Withesides.
Results: Let r be the radius and l be the length of the smallest edge. We have r greater or equal than l.
Definition A graph G is drawable with radius r if there exists an LMST drawing Gamma of G where r is the radius of the proximity region of each vertex.
Definition A graph is rho-LMST drawable if there exists a radius r such that the ratio between the length of the smallest edge of the drawing and the radius is equal to rho. rho=l/r.
- A tree with degree less or equal than 5 is 1/2n-drawable.
- A graph that is homeomorphic to the (n1 x n2) orthogonal (hexagonal) grid is 1/(2*(n-(n1*n2)+ epsilon)) drawable.
- A subgraph of the orthogonal grid is 1/f(n) drawable. f(n) to be compute
- An outerplanar graph with degree less or equal than 4 and whose dual graph is a path is 1/g(n) drawable. g(n) to be compute.
- Any planar graph with maximum degree 5 is homeomorphic to a planar graph with O(n3) vertices that is 1-drawable.
- Any planar graph with maximum degree 4 is homeomorphic to a planar graph with O(n2) vertices that is 1-drawable.
- For every graph G that is LMST-drawable the following inequalities hold on the maximum number maxE of edges that G can have 2n - 2 n1/2 <= maxE <= 2n -4.
- For every outerplanar graph O that is LMST-drawable the maximum number maxE of edges that O can have is (3n/2) - 2.
- There exists a planar graph with 5 vertices that is not LMST drawable.
- The problem of deciding whatever a general planar graph with maximum degree 5 can be realized as an LMST is NP-complete.
[PDF file]
Straight-line Orthogonal Bus Drawings
Question: The problem is that of computing nice drawings of diagrams containing buses If the main objective is to emphasize the bus structure we have to:- Draw buses as horizontal/vertical lines
- Draw edges to buses orthogonal and without bends
- Common nodes as well as buses do not intersect.
- Each edge connects its endpoints (the corresponding point and hor./vert. segment) and does not intersect any other node or bus.
- Edges are connected orthogonal to the bus segment.
Members: Emden Gansner, Michael Kaufmann, Martin Siebenhaller, Sue Withesides, Steve Wismath
Results: Define a 2-slob as having all common vertices of degree 2. For a 2-slob we define the busgraph as the underlying graph obtained by joining two buses if they share a common vertex of degree 2.
- If G is a tree then it can be drawn.
- A 2-slob S can be drawn if the collapsed graph is bipartite.
- Total 2-slobs cannot be drawn for b >= 9.
- A slob S is unidirectional iff: d(v) <= 2 and G is planar. As a consequence, it is possible to check in O(n) time if a 2-slob is unidirectionally drawable, and to determine a valid drawing. The following graph families (and subgraphs thereof) can be drawn: outerplanar, grid graphs. Counterexamples: Martin’s example. K2,4 can be drawn but not planarly.
Open Questions:
- What is the complexity of determining if a given 2 slob is drawable?
Some Nice Pictures:
 |  |
 |  |
 |