Aligned Drawings of Planar Graphs

Mchedlidze, Tamara and Radermacher, Marcel and Ignaz, Rutter (2017) Aligned Drawings of Planar Graphs. In: Graph Drawing and Network Visualization, GD 2017, September 25-27 , pp. 3-16(Official URL: https://doi.org/10.1007/978-3-319-73915-1_1).

Full text not available from this repository.

Abstract

Let G be a graph 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. [5], 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-hard but fixed-parameter tractable.

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.560 Geometry P Styles > P.540 Planar P Styles > P.720 Straight-line
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1587

Actions (login required)

View Item