Rectilinear planar layouts and bipolar orientations of planar graphs
From MaRDI portal
Publication:1085168
DOI10.1007/BF02187706zbMath0607.05027OpenAlexW2082205964WikidataQ61772230 ScholiaQ61772230MaRDI QIDQ1085168
Robert Endre Tarjan, Pierre Rosenstiehl
Publication date: 1986
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131001
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Visibility representations of boxes in 2.5 dimensions, A unified approach to visibility representations of planar graphs, Area requirement of visibility representations of trees, Visibility representations of four-connected plane graphs with near optimal heights, On the net-embeddability of graphs, Simultaneous visibility representations of plane \(st\)-graphs using L-shapes, A left-first search algorithm for planar graphs, An efficient parallel algorithm for finding rectangular duals of plane triangular graphs, On simultaneous straight-line grid embedding of a planar graph and its dual, 3-coloring arrangements of line segments with 4 slopes is hard, Grid embedding of 4-connected plane graphs, Optimal-area visibility representations of outer-1-plane graphs, Determining bar-representability for ordered weighted graphs, Drawing planar graphs using the canonical ordering, An annotated bibliography on 1-planarity, Skyscraper polytopes and realizations of plane triangulations, Algorithms for plane representations of acyclic digraphs, On Triangle Contact Graphs, Connectivity graphs of uncertainty regions, Special graph representation and visualization of semantic networks, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, 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, Good spanning trees in graph drawing, $st$-Orientations with Few Transitive Edges, A more compact visibility representation, A center transversal theorem for hyperplanes and applications to graph drawing, 1-Bend Upward Planar Drawings of SP-Digraphs, On Representation of Planar Graphs by Segments, Visibility representations of toroidal and Klein-bottle graphs, L-visibility drawings of IC-planar graphs, Two algorithms for finding rectangular duals of planar graphs, Bijections for Baxter families and related objects, \(\mathsf{T}\)-shape visibility representations of 1-planar 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, Dynamic maintenance of planar digraphs, with applications, Compact visibility representation of 4-connected plane graphs, Multilayer grid embeddings for VLSI, Minimum covering with travel cost, THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING, DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, 3D Visibility Representations of 1-planar Graphs, Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity, Width-Optimal Visibility Representations of Plane Graphs, Representations of graphs and networks (coding, layouts and embeddings), Testing approximate symmetry in the plane is NP-hard, On stable cutsets in claw-free graphs and planar graphs, Constrained visibility representations of graphs, The minimum broadcast time problem for several processor networks, A linear-time algorithm for drawing a planar graph on a grid, Area requirement and symmetry display of planar upward drawings, Unnamed Item, Constructing compact rectilinear planar layouts using canonical representation of planar graphs, Embedding-preserving rectangle visibility representations of nonplanar graphs, Drawing the planar dual, One strike against the min-max degree triangulation problem, Detecting and decomposing self-overlapping curves, Reconstructing sets of orthogonal line segments in the plane, On the number of upward planar orientations of maximal planar graphs, Some results on visibility graphs, Algorithms for computing a parameterized \(st\)-orientation, Star Partitions of Perfect Graphs, An experimental comparison of four graph drawing algorithms., Colored simultaneous geometric embeddings and universal pointsets, The one-round Voronoi game replayed, Improved visibility representation of plane graphs, Closed rectangle-of-influence drawings for irreducible triangulations, The DFS-heuristic for orthogonal graph drawing, NP-completeness of st-orientations for plane graphs, Balanced vertex-orderings of graphs, On triangulating planar graphs under the four-connectivity constraint, Planar bus graphs, Ortho-polygon visibility representations of embedded graphs, Upward planar morphs, Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights, Space-Efficient Planar Acyclicity Constraints, Representation of Planar Hypergraphs by Contacts of Triangles, On Aligned Bar 1-Visibility Graphs, Base-object location problems for base-monotone regions, Three Results on Frequency Assignment in Linear Cellular Networks, A dichotomy result for cyclic-order traversing games, Simultaneous Visibility Representations of Plane st-graphs Using L-shapes, Optimal \(st\)-orientations for plane triangulations, Geometric three-dimensional assignment problems, Algorithms for Drawing Planar p-petal Graphs, On 3D visibility representations of graphs with few crossings per edge, AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING, Three results on frequency assignment in linear cellular networks, Visibility representation of plane graphs via canonical ordering tree, Edge Partitions and Visibility Representations of 1-planar Graphs, Bipolar orientations revisited, How to draw a planar graph on a grid, The complexity of detecting crossingfree configurations in the plane
Uses Software
Cites Work
- Representing a planar graph by vertical lines joining different levels
- st-ordering the vertices of biconnected graphs
- Computing an st-numbering
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Finding Dominators in Directed Graphs
- Efficient Planarity Testing
- How to Draw a Graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
