Drawing Planar Graphs with Many Collinear Vertices
Given a planar graph G, what is the maximum number of collinear vertices in a planar straight-line drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The f
- PDF / 512,516 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 199 Views
3
University Roma Tre, Rome, Italy {dalozzo,frati,roselli}@dia.uniroma3.it 2 University of Ottawa, Ottawa, Canada [email protected] Karlsruhe Institute of Technology, Karlsruhe, Germany [email protected]
Abstract. Given a planar graph G, what is the maximum number of collinear vertices in a planar straight-line drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known: Every n-vertex planar graph has a planar straight-line √ drawingwith ˜ Ω( n) collinear vertices; for every n, there is an n-vertex planar graph whose every planar straight-line drawing has O(n0.986 ) collinear vertices; every n-vertex planar graph of treewidth at most two has a planar straight-line drawing with Θ(n) collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs, partially answering two problems posed by Ravsky and Verbitsky. Similar results are not possible for all bounded treewidth or bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.
1
Introduction
A set S of vertices in a planar graph G is collinear if G has a planar straightline drawing where all the vertices in S are collinear. Ravsky and Verbitsky [20] considered the problem of determining the maximum cardinality of collinear sets in planar graphs. A collinear set S is free if a total order 2, then λu (G) consists of curves λ0u , . . . , λ4u ; curve λ0u lies inside Cuz and connects puz with z2 , which is internal to Pz since Z > 2; λ1u coincides with path (z2 , . . . , zZ−1 ) (which is a single vertex if Z = 3); λ2u lies inside Cvz and connects zZ−1 with pv z ; λ3u coincides with λv (H); finally, λ4u lies inside Cuv and connects pu v with puv . Curves λ0u , λ2u , and λ4u are constructed as in Lemma 1. If Z = 2, then λu (G) consists of curves λ1u , . . . , λ4u ; curve λ1u lies inside Cuz and connects puz with pzz ; λ2u lies inside Cvz and connects pzz with pv z ; λ3u and λ4u are defined as in the case Z > 2. Curves λ1u , λ2u , and λ4u are constructed as in Lemma 1. This completes the construction of λu (G), λv (G), and λz (G). The curves λu (G), λv (G), and λz (G) are clearly proper. Lemmas 2 and 3 prove that they are good and pass through many vertices. We introduce three parameters for the latter proof: s(G) is the number of vertices the curves pass through (counting each vertex with a multiplicity equal to the number of curves that pass through it), x(G) is the number of internal vertices of type B none of the curves passes through, and h(G) is the number of B-chains of G. Lemma 2. Curves λu (G), λv (G), and λz (G) are good. Lemma 3. The following hold true if m ≥ 1: (1) a(G)+b(G)+c(G)+d(G) = m; (2) a(G) = c(G) + 2d(G) + 1; (3) h(G) ≤ 2c(G) + 3d(G) + 1; (4) x(G) ≤ b(G); (5) x(G) ≤ 3h(G); and (6) s(G) ≥ 3a(G) + b(G) − x(G). Proof Sketch
Data Loading...
