Relating Graph Thickness to Planar Layers and Bend Complexity

Authors Stephane Durocher, Debajyoti Mondal



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.10.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Stephane Durocher
Debajyoti Mondal

Cite AsGet BibTex

Stephane Durocher and Debajyoti Mondal. Relating Graph Thickness to Planar Layers and Bend Complexity. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.10

Abstract

The thickness of a graph G = (V, E) with n vertices is the minimum number of planar subgraphs of G whose union is G. A polyline drawing of G in R^2 is a drawing Gamma of G, where each vertex is mapped to a point and each edge is mapped to a polygonal chain. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of Gamma is the maximum number of bends per edge in Gamma, and the layer complexity of Gamma is the minimum integer r such that the set of polygonal chains in Gamma can be partitioned into r disjoint sets, where each set corresponds to a planar polyline drawing. Let G be a graph of thickness t. By Fáry’s theorem, if t = 1, then G can be drawn on a single layer with bend complexity 0. A few extensions to higher thickness are known, e.g., if t = 2 (resp., t > 2), then G can be drawn on t layers with bend complexity 2 (resp., 3n + O(1)). In this paper we present an elegant extension of Fáry's theorem to draw graphs of thickness t > 2. We first prove that thickness-t graphs can be drawn on t layers with 2.25n + O(1) bends per edge. We then develop another technique to draw thickness-t graphs on t layers with reduced bend complexity for small values of t, e.g., for t in {3, 4}, the bend complexity decreases to O(sqrt(n)). Previously, the bend complexity was not known to be sublinear for t > 2. Finally, we show that graphs with linear arboricity k can be drawn on k layers with bend complexity 3*(k-1)*n/(4k-2).
Keywords
  • Graph Drawing
  • Thickness
  • Geometric Thickness
  • Layers; Bends

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Melanie Badent, Emilio Di Giacomo, and Giuseppe Liotta. Drawing colored graphs on colored points. Theoretical Computer Science, 408(2-3):129-142, 2008. Google Scholar
  2. Reuven Bar-Yehuda and Sergio Fogel. Partitioning a sequence into few monotone subsequences. Acta Informatica, 35(5):421-440, 1998. Google Scholar
  3. János Barát, Jiří Matoušek, and David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness. Electronic Journal of Combinatorics, 13(R3), 2006. Google Scholar
  4. Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter. Simultaneous embedding of planar graphs. In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 11, pages 349-380. CRC Press, August 2013. Google Scholar
  5. Peter Braß, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan Ismailescu, Stephen G. Kobourov, Anna Lubiw, and Joseph S. B. Mitchell. On simultaneous planar graph embeddings. Computational Geometry, 36(2):117-130, 2007. Google Scholar
  6. Michael B. Dillencourt, David Eppstein, and Daniel S. Hirschberg. Geometric thickness of complete graphs. Journal of Graph Algorithms and Applications, 4(3):5-17, 2000. Google Scholar
  7. Vida Dujmović and David R. Wood. Graph treewidth and geometric thickness parameters. Discrete & Computational Geometry, 37(4):641-670, 2007. Google Scholar
  8. Christian A. Duncan. On graph thickness, geometric thickness, and separator theorems. Computational Geometry, 44(2):95-99, 2011. Google Scholar
  9. Christian A. Duncan, David Eppstein, and Stephen G. Kobourov. The geometric thickness of low degree graphs. In Proceedings of the 20th ACM Symposium on Computational Geometry (SoCG), pages 340-346. ACM, 2004. Google Scholar
  10. Stephane Durocher, Ellen Gethner, and Debajyoti Mondal. Thickness and colorability of geometric graphs. Computational Geometry: Theory and Applications, 56:1-18, 2016. Google Scholar
  11. Stephane Durocher and Debajyoti Mondal. Relating graph thickness to planar layers and bend complexity, 2016. URL: http://arxiv.org/abs/1602.07816.
  12. Hikoe Enomoto and Miki Shimabara Miyauchi. Embedding graphs into a three page book with O(m log n) crossings of edges over the spine. SIAM Journal on Discrete Mathematics, 12(3):337-341, 1999. Google Scholar
  13. David Eppstein. Separating thickness from geometric thickness. In János Pach, editor, Towards a Theory of Geometric Graphs. American Mathematical Society, 2004. Google Scholar
  14. Paul Erdös and George Szekeres. A combinatorial theorem in geometry. Compositio Math., 2:463-470, 1935. Google Scholar
  15. Cesim Erten and Stephen G. Kobourov. Simultaneous embedding of planar graphs with few bends. Journal of Graph Algorithms and Applications, 9(3):347-364, 2005. Google Scholar
  16. István Fáry. On straight-line representation of planar graphs. Acta Sci. Math. (Szeged), 11:229-233, 1948. Google Scholar
  17. Emilio Di Giacomo and Giuseppe Liotta. Simultaneous embedding of outerplanar graphs, paths, and cycles. International Journal of Computational Geometry &Applications, 17(2):139-160, 2007. Google Scholar
  18. Taylor Gordon. Simultaneous embeddings with vertices mapping to pre-specified points. In Proceedings of the 18th Annual International Conference on Computing and Combinatorics (COCOON), volume 7434 of LNCS, pages 299-310. Springer, 2012. Google Scholar
  19. Joseph B. Kruskal. Monotonic subsequences. Proceedings of the American Mathematical Society, 4:264-274, 1953. Google Scholar
  20. János Pach and Rephael Wenger. Embedding planar graphs at fixed vertex locations. Graphs &Combinatorics, 17(4):717-728, 2001. Google Scholar
  21. David R. Wood. Geometric thickness in a grid. Discrete Mathematics, 273(1-3):221-234, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail