Rectilinear planar layouts and bipolar orientations of planar graphs
From MaRDI portal
The authors propose a linear-time algorithm for generating a planar layout of a planar graph in which vertices (edges) are represented by horizontal (vertical) line segments, all endpoints of the segments having integer coordinates. The new algorithm, a variant of one by \textit{Otten} and \textit{van Wijk} [Circuits and Systems, Proc. IEEE Int. Symp. 914-918 (1978)] generally produces a more compact layout and, at the same time allows the dual graph to be laid out in an interlocking way. It is based on the concept of a bipolar orientation of a planar graph G with two distinguished vertices s and t; it is obtained by directing each edge of G so as to obtain a unique source (s) and unique sink (t). Relationships among bipolar orientations of a planar graph are also discussed.
Recommendations
- Proper orientations of planar bipartite graphs
- Mixed linear layouts of planar graphs
- scientific article; zbMATH DE number 4049689
- On the Optimal Layout of Planar Graphs with Fixed Boundary
- scientific article; zbMATH DE number 2159644
- Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
- Constructing compact rectilinear planar layouts using canonical representation of planar graphs
- Acyclic and Totally Cyclic Orientations in Planar Graphs
- Rectangular duals of planar graphs
- Planar linear arrangements of outerplanar graphs
Cites work
- Computing an st-numbering
- Efficient Planarity Testing
- Finding Dominators in Directed Graphs
- How to Draw a Graph
- scientific article; zbMATH DE number 3885930 (Why is no real title available?)
- scientific article; zbMATH DE number 3949734 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3531439 (Why is no real title available?)
- scientific article; zbMATH DE number 3315017 (Why is no real title available?)
- scientific article; zbMATH DE number 3047038 (Why is no real title available?)
- Representing a planar graph by vertical lines joining different levels
- st-ordering the vertices of biconnected graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Cited in
(only showing first 100 items - show all)- Optimal st-orientations for plane triangulations
- Three results on frequency assignment in linear cellular networks
- Visibility representation of plane graphs via canonical ordering tree
- A unified approach to visibility representations of planar graphs
- Algorithms for plane representations of acyclic digraphs
- Representations of graphs and networks (coding, layouts and embeddings)
- Testing approximate symmetry in the plane is NP-hard
- Constrained visibility representations of graphs
- Area requirement and symmetry display of planar upward drawings
- Constructing compact rectilinear planar layouts using canonical representation of planar graphs
- Drawing the planar dual
- Detecting and decomposing self-overlapping curves
- Some results on visibility graphs
- Geometric three-dimensional assignment problems
- The complexity of detecting crossingfree configurations in the plane
- Grid embedding of 4-connected plane graphs
- Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
- 3-coloring arrangements of line segments with 4 slopes is hard
- \(\mathsf{T}\)-shape visibility representations of 1-planar graphs
- Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
- Balanced vertex-orderings of graphs
- Bipolar orientations revisited
- A left-first search algorithm for planar graphs
- An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
- Determining bar-representability for ordered weighted graphs
- Drawing planar graphs using the canonical ordering
- Special graph representation and visualization of semantic networks
- A center transversal theorem for hyperplanes and applications to graph drawing
- Embedding-preserving rectangle visibility representations of nonplanar graphs
- Optimal-area visibility representations of outer-1-plane graphs
- Colored anchored visibility representations in 2D and 3D space
- 1-bend upward planar slope number of SP-digraphs
- Homotopy height, grid-major height and graph-drawing height
- On the number of upward planar orientations of maximal planar graphs
- NP-completeness of st-orientations for plane graphs
- On 3D visibility representations of graphs with few crossings per edge
- An annotated bibliography on 1-planarity
- Skyscraper polytopes and realizations of plane triangulations
- Bijections for Baxter families and related objects
- An experimental comparison of four graph drawing algorithms.
- Linear layout of directed grid graph
- The three-phase method: a unified approach to orthogonal graph drawing
- Drawing directed acyclic graphs: an experimental study
- Space-efficient planar acyclicity constraints. A declarative pearl
- Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
- Algorithms for Drawing Planar p-petal Graphs
- Area requirement of visibility representations of trees
- 1-bend upward planar drawings of SP-digraphs
- Simultaneous visibility representations of plane st-graphs using L-shapes
- Orientation-Constrained Rectangular Layouts
- On Representation of Planar Graphs by Segments
- Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights
- Three Results on Frequency Assignment in Linear Cellular Networks
- scientific article; zbMATH DE number 4049689 (Why is no real title available?)
- On Triangle Contact Graphs
- Compact visibility representation of 4-connected plane graphs
- Minimum covering with travel cost
- 3D Visibility Representations of 1-planar Graphs
- scientific article; zbMATH DE number 1858605 (Why is no real title available?)
- Edge Partitions and Visibility Representations of 1-planar Graphs
- On triangulating planar graphs under the four-connectivity constraint
- A dichotomy result for cyclic-order traversing games
- On the net-embeddability of graphs
- Width-Optimal Visibility Representations of Plane Graphs
- Representation of Planar Hypergraphs by Contacts of Triangles
- Colored simultaneous geometric embeddings and universal pointsets
- AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING
- On Aligned Bar 1-Visibility Graphs
- Upward planar morphs
- The DFS-heuristic for orthogonal graph drawing
- Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario
- Good acyclic orientations of 4‐regular 4‐connected graphs
- \(st\)-orientations with few transitive edges
- $st$-Orientations with Few Transitive Edges
- A more compact visibility representation
- Visibility representations of toroidal and Klein-bottle graphs
- Two algorithms for finding rectangular duals of planar graphs
- Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
- The minimum broadcast time problem for several processor networks
- A linear-time algorithm for drawing a planar graph on a grid
- One strike against the min-max degree triangulation problem
- Reconstructing sets of orthogonal line segments in the plane
- Plattenbauten: touching rectangles in space
- The one-round Voronoi game replayed
- Improved visibility representation of plane graphs
- Closed rectangle-of-influence drawings for irreducible triangulations
- A census of graph-drawing algorithms based on generalized transversal structures
- Planar bus graphs
- On plane cycles in geometric multipartite graphs
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Base-object location problems for base-monotone regions
- How to draw a planar graph on a grid
- Visibility representations of four-connected plane graphs with near optimal heights
- On simultaneous straight-line grid embedding of a planar graph and its dual
- Good spanning trees in graph drawing
- L-visibility drawings of IC-planar graphs
- Dynamic maintenance of planar digraphs, with applications
- Multilayer grid embeddings for VLSI
- Not being (super)thin or solid is hard: A study of grid Hamiltonicity
- On stable cutsets in claw-free graphs and planar graphs
This page was built for publication: Rectilinear planar layouts and bipolar orientations of planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085168)
