Document Open Access Logo

Cubic Planar Graphs That Cannot Be Drawn On Few Lines

Author David Eppstein

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.32.pdf
  • Filesize: 0.82 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Human-centered computing → Graph drawings
Keywords
  • graph drawing
  • universal point sets
  • collinearity

Metrics

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

Abstract

For every integer l, we construct a cubic 3-vertex-connected planar bipartite graph G with O(l^3) vertices such that there is no planar straight-line drawing of G whose vertices all lie on l lines. This strengthens previous results on graphs that cannot be drawn on few lines, which constructed significantly larger maximal planar graphs. We also find apex-trees and cubic bipartite series-parallel graphs that cannot be drawn on a bounded number of lines.

Cite As Get BibTex

David Eppstein. Cubic Planar Graphs That Cannot Be Drawn On Few Lines. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.32

Author Details

David Eppstein
  • Computer Science Department, University of California, Irvine, USA

Funding

  • Eppstein, David: Supported in part by NSF grants CCF-1618301 and CCF-1616248.

References

  1. Hans-Jürgen Bandelt, Victor Chepoi, and David Eppstein. Combinatorics and geometry of finite and infinite squaregraphs. SIAM Journal on Discrete Mathematics, 24(4):1399-1440, 2010. URL: http://dx.doi.org/10.1137/090760301.
  2. Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood. Track layouts, layered path decompositions, and leveled planarity. Algorithmica, 2018. URL: http://dx.doi.org/10.1007/s00453-018-0487-5.
  3. Therese Biedl, William Evans, Stefan Felsner, Sylvain Lazard, Henk Meijer, Pavel Valtr, Sue Whitesides, Steve Wismath, and Alexander Wolff. Line and plane cover numbers revisited. Manuscript, 2019. Google Scholar
  4. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. The complexity of drawing graphs on few lines and few planes. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures: 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, volume 10389 of Lecture Notes in Computer Science, pages 265-276. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_23.
  5. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Oleg Verbitsky, and Alexander Wolff. Drawing graphs on few lines and few planes. In Yifan Hu and Martin Nöllenburg, editors, Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, volume 9801 of Lecture Notes in Computer Science, pages 166-180. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-50106-2_14.
  6. Danny Dolev, Tom Leighton, and Howard Trickey. Planar embedding of planar graphs. Advances in Computing Research, 2:147-161, 1984. URL: https://noodle.cs.huji.ac.il/~dolev/pubs/planar-embed.pdf.
  7. Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood. Minor-closed graph classes with bounded layered pathwidth. in preparation, 2018. Google Scholar
  8. Vida Dujmović, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances Rosamond, Sue Whitesides, and David R. Wood. On the parameterized complexity of layered graph drawing. Algorithmica, 52(2):267-292, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9151-1.
  9. Vida Dujmović, Pat Morin, and David R. Wood. Path-width and three-dimensional straight-line grid drawings of graphs. In Michael T. Goodrich and Stephen G. Kobourov, editors, Graph Drawing: 10th International Symposium, GD 2002, Irvine, CA, USA, August 26-28, 2002, Revised Papers, volume 2528 of Lecture Notes in Computer Science, pages 42-53. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-36151-0_5.
  10. Vida Dujmović, Attila Pór, and David R. Wood. Track layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):497-521, 2004. Google Scholar
  11. Vida Dujmović and David R. Wood. Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci., 7(1):155-201, 2005. Google Scholar
  12. Peter Eades and Sue Whitesides. Drawing graphs in two layers. Theoretical Computer Science, 131(2):361-374, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90179-1.
  13. Peter Eades and Nicholas C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379-403, 1994. URL: http://dx.doi.org/10.1007/BF01187020.
  14. David Eppstein. Forbidden Configurations in Discrete Geometry. Cambridge University Press, 2018. Theorem 16.13. Google Scholar
  15. Stefan Felsner, Giuseppe Liotta, and Stephen Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. Journal of Graph Algorithms and Applications, 7(4):363-398, 2003. URL: http://dx.doi.org/10.7155/jgaa.00075.
  16. Oksana Firman, Fabian Lipp, Laura Straube, and Alexander Wolff. Examining weak line covers with two lines in the plane (poster abstract). In Graph Drawing and Network Visualization: 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Revised Selected Papers, Lecture Notes in Computer Science. Springer, 2018. to appear. Google Scholar
  17. Fabrizio Frati and Maurizio Patrignani. A note on minimum-area straight-line drawings of planar graphs. In Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers, volume 4875 of Lecture Notes in Computer Science, pages 339-344. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77537-9_33.
  18. Saunders Mac Lane. A structural characterization of planar combinatorial graphs. Duke Mathematical Journal, 3(3):460-472, 1937. URL: http://dx.doi.org/10.1215/S0012-7094-37-00336-3.
  19. Alexander Ravsky and Oleg Verbitsky. On collinear sets in straight-line drawings. In Petr Kolman and Jan Kratochvíl, editors, Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011, Revised Papers, volume 6986 of Lecture Notes in Computer Science, pages 295-306. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25870-1_27.
  20. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact