Aligned drawings of planar graphs

T. Mchedlidze, M. Radermacher, I. Rutter

Research output: Contribution to journalArticleAcademic

233 Downloads (Pure)

Abstract

Let G be a graph topological embedded in the plane and let A be an arrangement of pseudolines intersecting the drawing of G . An aligned drawing of G and A is a planar polyline drawing Γ of G with an arrangement A of lines so that Γ and A are homeomorphic to G and A . We show that if A is stretchable and every edge e either entirely lies on a pseudoline or intersects at most one pseudoline, then G and A have a straight-line aligned drawing. In order to prove these results, we strengthen the result of Da Lozzo et al., and prove that a planar graph G and a single pseudoline L have an aligned drawing with a prescribed convex drawing of the outer face. We also study the more general version of the problem where only a set of vertices is given and we need to determine whether they can be collinear. We show that the problem is NP -complete but fixed-parameter tractable.
Original languageEnglish
Article number1708.08778
Number of pages24
JournalarXiv
Issue number1708.08778
Publication statusPublished - 2017

Bibliographical note

Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

Keywords

  • cs.DS
  • cs.CG

Fingerprint

Dive into the research topics of 'Aligned drawings of planar graphs'. Together they form a unique fingerprint.

Cite this