Open RectangleofInfluence Drawings of Nontriangulated Planar GraphsAlamdari, Soroush and Biedl, Therese (2013) Open RectangleofInfluence Drawings of Nontriangulated Planar Graphs. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 102113(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractA straight line drawing of a graph is an open weak rectangleofinfluence (RI) drawing if there is no vertex in the relative interior of the axis parallel rectangle induced by the end points of each edge. Despite recent interest of the graph drawing community in rectangleofinfluence drawings, no algorithm is known to test whether a graph has a planar open weak RIdrawing. In a recent paper, we showed how to test, for innertriangulated planar graphs, whether they have a planar open weak RIdrawing with a nonaligned frame, i.e., the graph obtained from removing the interior of every filled triangle is drawn such that no two vertices have the same coordinate. In this paper, we generalize this to all planar graphs with a fixed planar embedding, even if some interior faces are not triangles. On the other hand, we show that if the planar embedding is not fixed, then deciding if a given planar graph has an open weak RIdrawing is NPcomplete. NPcompleteness holds even for open weak RIdrawings with nonaligned frames.
Actions (login required)
