Planar Graphs as VPG-Graphs

Chaplick, Steven and Ueckerdt, Torsten (2013) Planar Graphs as VPG-Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 174-186 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_16).

Full text not available from this repository.

Abstract

A graph is $B_k-VPG$ when it has an intersection representation by paths in a rectangular grid with at most k bends (turns). It is known that all planar graphs are $B_3-VPG$ and this was conjectured to be tight. We disprove this conjecture by showing that all planar graphs are $B_2-VPG$. We also show that the 4-connected planar graphs are a subclass of the intersection graphs of Z-shapes (i.e., a special case of $B_2-VPG$). Additionally, we demonstrate that a $B_2-VPG$ representation of a planar graph can be constructed in $O(n^{3/2} )$ time. We further show that the triangle-free planar graphs are contact graphs of: L-shapes, Γ-shapes, vertical segments, and horizontal segments (i.e., a special case of contact $B_1-VPG$). From this proof we gain a new proof that bipartite planar graphs are a subclass of 2-DIR.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_16
Classifications:G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line
Z Theory > Z.250 Geometry
ID Code:1308

Repository Staff Only: item control page

References

Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G.: Proportional Contact Representations of Planar Graphs. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 26–38. Springer, Heidelberg (2012)

Asinowski, A., Cohen, E., Golumbic, M.C., Limouzy, V., Lipshteyn, M., Stern, M.: Vertex intersection graphs of paths on a grid. J. Graph Algorithms Appl. 16(2), 129–150 (2012)

Ben-Arroyo Hartman, I., Newman, I., Ziv, R.: On grid intersection graphs. Discrete Math. 87(1), 41–52 (1991)

de Castro, N., Cobos, F.J., Dana, J.C., Márquez, A., Noy, M.: Triangle-free planar graphs and segment intersection graphs. J. Graph Algorithms Appl. 6(1), 7–26 (2002)

Chalopin, J., Gonçalves, D., Ochem, P.: Planar graphs are in 1-STRING. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 609–617 (2007)

Chalopin, J., Gonçalves, D.: Every planar graph is the intersection graph of segments in the plane: extended abstract. In: 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 631–638 (2009)

Ehrlich, G., Even, S., Tarjan, R.: Intersection graphs of curves in the plane. J. Comb. Theory, Ser. B 21(1), 8–20 (1976)

Eppstein, D.: Regular labelings and geometric structures. In: 22nd Canadian Conference on Computational Geometry, CCCG 2010, pp. 125–130 (2010)

de Fraysseix, H., Ossona de Mendez, P.: Representations by contact and intersection of segments. Algorithmica 47(4), 453–463 (2007)

de Fraysseix, H., Ossona de Mendez, P., Pach, J.: Representation of planar graphs by segments. Intuitive Geometry 63, 109–117 (1991)

de Fraysseix, H., Ossona de Mendez, P., Rosenstiehl, P.: On triangle contact graphs. Combinatorics, Probability & Computing 3, 233–246 (1994)

Fusy, E.: Combinatoire des cartes planaires et applications algorithmiques. PhD Thesis (2007)

Fusy, E.: Transversal structures on triangulations: A combinatorial study and straight-line drawings. Discrete Math. 309(7), 1870–1894 (2009)

Gavenčiak, T.: Private communication: Small planar graphs are L-graphs (2012)

He, X.: On finding the rectangular duals of planar triangular graphs. SIAM J. Comput. 22, 1218–1226 (1993)

Heldt, D., Knauer, K., Ueckerdt, T.: On the Bend-Number of Planar and Outerplanar Graphs. In: Fernández-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 458–469. Springer, Heidelberg (2012)

Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172(1-2), 175–193 (1997)

Kobourov, S., Ueckerdt, T., Verbeek, K.: Combinatorial and geometric properties of laman graphs (2012)

Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig. Math.-Phys. Klasse 88, 141–164 (1936)

Koźmiński, K., Kinnen, E.: Rectangular dual of planar graphs. Networks 15(2), 145–157 (1985)

Kratochvíl, J., Matoušek, J.: Intersection graphs of segments. J. Comb. Theory, Ser. B 62(2), 289–315 (1994)

Scheinerman, E.R.: Intersection Classes and Multiple Intersection Parameters of Graphs. Ph.D. thesis. Princeton University (1984)

Sinden, F.: Topology of thin film circuits. Bell System Tech. J. 45, 1639–1662 (1966)

Sun, Y., Sarrafzadeh, M.: Floorplanning by graph dualization: L-shaped modules. Algorithmica 10, 429–456 (1993)

Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory, Ser. B 40(1), 9–20 (1986)

Ungar, P.: On diagrams representing graphs. J. London Math. Soc. 28, 336–342 (1953)

West, D.: Open problems. SIAM J. Discrete Math. Newslett. 2, 10–12 (1991)