Introduction. A pseudoline is formed from a line by stretching the plane without tearing: it is the image of a line under a homeomorphism of the plane [13]. In arrangements of pseudolines, pairs of pseudolines intersect at most once and cross at their intersections. Pseudoline arrangements can be used to model sorting networks [1], tilings of convex polygons by rhombi [4], and graphs that have distance-preserving embeddings into hypercubes [6]. They are also closely related to oriented matroids [11]. We consider here the visualization of arrangements using well-shaped curves. Primarily, we study weak outerplanar pseudoline arrangements. An arrangement is weak if it does not necessarily have a crossing for every pair of pseudolines [12], and outerplanar if every crossing is part of an unbounded face of the arrangement. We show that these arrangements can be drawn with all curves convex, either as polygonal chains with at most two bends per pseudoline or as semicircles above a line. Arbitrary pseudolines can also be drawn as convex curves, but may require linearly many bends. Related Work. Several results related to the visualization of pseudoline arrangements are known. In wiring diagrams, pseudolines are drawn on parallel horizontal lines, with crossings on short line segments that connect pairs of horizontal lines [10]. The graphs of arrangements have drawings in small grids [8] and the dual graphs of weak arrangements have drawings in which each bounded face is centrally symmetric [5]. The pseudoline arrangements in which each pseudoline is a translated quadrant can be used to visualize learning spaces representing the states of a human learner [7]. Researchers in graph drawing have also studied force-directed methods for schematizing systems of curves representing metro maps by replacing each curve by a spline; these curves are not necessarily pseudolines, but they typically have few crossings [9]. Results. Below we state our results for outerplanar and arbitrary arrangements. Theorem 1. Every weak outerplanar pseudoline arrangement may be represented by
Several results related to the visualization of pseudoline arrangements are known. In , pseudolines are drawn on parallel horizontal lines, with crossings on short line segments that connect pairs of horizontal lines @cite_14 . Using a method based on compaction of wiring diagrams, the graphs of pseudoline arrangements may be given straight line drawings in small grids @cite_0 . The planar dual graph of a weak pseudoline arrangement may be characterized as having drawings in which each bounded face is a centrally symmetric polygon @cite_9 . The pseudoline arrangements in which each pseudoline is a translated quadrant can be used to visualize , representing the possible states of knowledge of a human learner @cite_8 . Researchers in graph drawing have also studied force-directed methods for schematizing systems of curves representing metro maps by replacing each curve by a spline; these curves are not necessarily pseudolines, but they typically have few crossings @cite_3 .
@cite_14 @cite_8 @cite_9 @cite_3 @cite_0
2091316025 2568823708 1543380145 2103359219 1503918231
We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area On 7 6. No known input causes our algorithm to use area Ωn 1+e for any e>0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle. We establish a duality principle for arrangements of pseudolines in the projective plane, and thereby prove the conjecture of Burr, Grunbaum, and Sloane that the solution of the ''orchard problem'' for pseudoline arrangements and the solution [email protected]?(p) of the dual problem are equal. The automatic layout of metro maps has been investigated quite intensely over the last few years. Previous work has focused on the octilinear drawing style where edges are drawn horizontally, vertically, or diagonally at 45°. Inspired by manually created curvy metro maps, we advocate the use of the curvilinear drawing style; we draw edges as Bezier curves. Since we forbid metro lines to bend (even in stations), the user of such a map can trace the metro lines easily. In order to create such drawings, we use the force-directed framework. Our method is the first that directly represents and operates on edges as curves. Right Angle Crossing (RAC) drawings are polyline drawings where each crossing forms four right angles. RAC drawings have been introduced because cognitive experiments provided evidence that increasing the number of crossings does not decrease the readability of the drawing if the edges cross at right angles. We investigate to what extent RAC drawings can help in overcoming the limitations of widely adopted planar graph drawing conventions, providing both positive and negative results. First, we prove that there exist acyclic planar digraphs not admitting any straight-line upward RAC drawing and that the corresponding decision problem is NP-hard. Also, we show digraphs whose straight-line upward RAC drawings require exponential area. Second, we study if RAC drawings allow us to draw bounded-degree graphs with lower curve complexity than the one required by more constrained drawing conventions. We prove that every graph with vertex-degree at most 6 (at most 3) admits a RAC drawing with curve complexity 2 (resp. 1) and with quadratic area. Third, we consider a natural non-planar generalization of planar embedded graphs. Here we give bounds for curve complexity and area different from the ones known for planar embeddings.