On Rectilinear Drawing of GraphsEades, Peter and Hong, SeokHee and Poon, SheungHung (2010) On Rectilinear Drawing of Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 2225, 2009 , pp. 232243(Official URL: http://dx.doi.org/10.1007/9783642118050_23). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_23
AbstractA rectilinear drawing is an orthogonal grid drawing without bends, possibly with edge crossings, without any overlapping between edges, between vertices, or between edges and vertices. Rectilinear drawings without edge crossings (planar rectilinear drawings) have been extensively investigated in graph drawing. Testing rectilinear planarity of a graph is NPcomplete [10]. Restricted cases of the planar rectilinear drawing problem, sometimes called the “nobend orthogonal drawing problem”, have been well studied (see, for example, [13,14,15]). In this paper, we study the problem of general nonplanar rectilinear drawing; this problem has not received as much attention as the planar case. We consider a number of restricted classes of graphs and obtain a polynomial time algorithm, NPhardness results, an FPT algorithm, and some bounds. We deﬁne a structure called a “4cycle block”. We give a linear time algorithm to test whether a graph that consists of a single 4cycle block has a rectilinear drawing, and draw it if such a drawing exists. We show that the problem is NPhard for the graphs that consist of 4cycle blocks connected by single edges, as well as the case where each vertex has degree 2 or 4. We present a linear time ﬁxedparameter tractable algorithm to test whether a degree4 graph has a rectilinear drawing, where the parameter is the number of degree3 and degree4 vertices of the graph. We also present a lower bound on the area of rectilinear drawings, and a upper bound on the number of edges.
Actions (login required)
