Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph

Schaefer, Marcus (2014) Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 13-24(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_2).

Full text not available from this repository.

Abstract

Given a graph G and a subset F ⊆ E(G) of its edges, is there a drawing of G in which all edges of F are free of crossings? We show that this question can be solved in polynomial time using a Hanani-Tutte style approach. If we require the drawing of G to be straight-line, but allow up to one crossing along each edge in F, the problem turns out to be as hard as the existential theory of the real numbers.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-662-45803-7_2
Classifications:	G Algorithms and Complexity > G.420 Crossings G Algorithms and Complexity > G.770 Planarity Testing P Styles > P.600 Poly-line P Styles > P.720 Straight-line Z Theory > Z.750 Topology
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1418

Actions (login required)

View Item