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 2426, 2014 , pp. 1324(Official URL: http://dx.doi.org/10.1007/9783662458037_2). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_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 HananiTutte style approach. If we require the drawing of G to be straightline, 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)
