Picking Planar Edges; or, Drawing a Graph with a Planar SubgraphSchaefer, 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.
Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_2
AbstractGiven 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.
Actions (login required)
|