Abstract
The bend-number b(G) of a graph G is the minimum k such that G may be represented as the edge intersection graph of a set of grid paths with at most k bends. We confirm a conjecture of Biedl and Stern showing that the maximum bend-number of outerplanar graphs is 2. Moreover we improve the formerly known lower and upper bound for the maximum bend-number of planar graphs from 2 and 5 to 3 and 4, respectively.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Asinowski, A., Suk, A.: Edge intersection graphs of systems of paths on a grid with a bounded number of bends. Discrete Appl. Math. 157(14), 3174–3180 (2009)
Biedl, T., Stern, M.: On edge-intersection graphs of k-bend paths in grids. Discrete Math. Theor. Comput. Sci. 12(1), 1–12 (2010)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1-2), 1–45 (1998)
Brady, M.L., Sarrafzadeh, M.: Stretching a knock-knee layout for multilayer wiring. IEEE Trans. Comput. 39(1), 148–151 (1990)
de Fraysseix, H., Ossona de Mendez, P., Rosenstiehl, P.: On triangle contact graphs. Combin. Probab. Comput. 3(2), 233–246 (1994)
El-Mallah, E.S., Colbourn, C.J.: On two dual classes of planar graphs. Discrete Math. 80(1), 21–40 (1990)
Golumbic, M.C., Lipshteyn, M., Stern, M.: Representing edge intersection graphs of paths on degree 4 trees. Discrete Math. 308(8), 1381–1387 (2008)
Golumbic, M.C., Lipshteyn, M., Stern, M.: Edge intersection graphs of single bend paths on a grid. Networks 54(3), 130–138 (2009)
Gonçalves, D., Ochem, P.: On some arboricities in planar graphs. Electronic Notes in Discrete Mathematics 22, 427–432 (2005), 7th International Colloquium on Graph Theory
Gyárfás, A., West, D.: Multitrack interval graphs. In: Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, vol. 109, pp. 109–116 (1995)
Harary, F., Trotter Jr., W.T.: On double and multiple interval graphs. J. Graph Theory 3(3), 205–211 (1979)
Heldt, D., Knauer, K., Ueckerdt, T.: Edge-intersection graphs of grid paths – the bend-number, preprint, arXiv:1009.2861v1 (math.CO) (2010)
Heldt, D., Knauer, K., Ueckerdt, T.: On the bend-number of planar and outerplanar graphs, preprint, arXiv:1112.3353v1 (math.CO) (2011)
Kostochka, A.V., West, D.B.: Every outerplanar graph is the union of two interval graphs. In: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, vol. 139, pp. 5–8 (1999)
Koźmiński, K., Kinnen, E.: Rectangular dual of planar graphs. Networks 15(2), 145–157 (1985)
Lai, Y.-T., Leinwand, S.M.: An algorithm for building rectangular floor-plans. In: 21st Design Automation Conference (DAC 1984), pp. 663–664 (1984)
Ries, B.: Some properties of edge intersection graphs of single bend path on a grid. Electronic Notes in Discrete Mathematics 34, 29–33 (2009); European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009)
Scheinerman, E.R., West, D.B.: The interval number of a planar graph: three intervals suffice. J. Combin. Theory Ser. B 35(3), 224–239 (1983)
Ungar, P.: On diagrams representing maps. Journal of the London Mathematical Society 28, 336–342 (1953)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heldt, D., Knauer, K., Ueckerdt, T. (2012). On the Bend-Number of Planar and Outerplanar Graphs. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-29344-3_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29343-6
Online ISBN: 978-3-642-29344-3
eBook Packages: Computer ScienceComputer Science (R0)