How to draw a planar graph on a grid

From MaRDI portal

Publication:804582

Jump to:navigation, search

DOI10.1007/BF02122694zbMath0728.05016OpenAlexW2003525146WikidataQ57253826 ScholiaQ57253826MaRDI QIDQ804582

Richard Pollack, Hubert de Fraysseix, János Pach

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02122694

zbMATH Keywords

planar graph planar grid

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Drawing Halin-graphs with small height, A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems, Unnamed Item, Drawing Planar Graphs on Area, Connectivity check in 3-connected planar graphs with obstacles, A Polynomial Bound for Untangling Geometric Planar Graphs, Upward Straight-Line Embeddings of Directed Graphs into Point Sets, Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges, A Lower Bound on the Area Requirements of Series-Parallel Graphs, Conflict-Free Coloring of Intersection Graphs, Grid obstacle representation of graphs, On Triangle Contact Graphs, Drawing Planar Graphs with Few Geometric Primitives, Universal slope sets for 1-bend planar drawings, On Point-Sets That Support Planar Graphs, Small Point Sets for Simply-Nested Planar Graphs, Approximate Proximity Drawings, Straight-line drawings of 1-planar graphs, Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario, An exponential bound for simultaneous embeddings of planar graphs, Rectangular partitions of a rectilinear polygon, The computational complexity of knot genus in a fixed 3‐manifold, Strictly-convex drawings of 3-connected planar graphs, A more compact visibility representation, An annotated review on graph drawing and its applications, Non-aligned Drawings of Planar Graphs, Snapping Graph Drawings to the Grid Optimally, Drawing Graphs on Few Lines and Few Planes, Bitonic st-orderings for Upward Planar Graphs, On the Density of Non-simple 3-Planar Graphs, Visibility representations of toroidal and Klein-bottle graphs, Optimal polygonal representation of planar graphs, On-line convex planarity testing, Two algorithms for finding rectangular duals of planar graphs, A Note on Universal Point Sets for Planar Graphs, Graph Stories in Small Area, The number of Reidemeister moves needed for unknotting, An Experimental Study on the Ply Number of Straight-Line Drawings, Computing cartograms with optimal complexity, An Experimental Study on the Ply Number of Straight-line Drawings, Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges, SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS, Planar Bichromatic Bottleneck Spanning Trees, Compact Grid Representation of Graphs, Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area, On local transformations in plane geometric graphs embedded on small grids, Listing All Plane Graphs, Rectangular grid drawings of plane graphs, Drawing planar graphs with circular arcs, CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS, Unnamed Item, Unnamed Item, \(k\)-spine, 1-bend planarity, Triangulating planar graphs while minimizing the maximum degree, Universal slope sets for upward planar drawings, Compact drawings of 1-planar graphs with right-angle crossings and few bends, Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n logn) Area (Extended Abstract), Universal slope sets for upward planar drawings, CONVEX DRAWINGS OF INTERNALLY TRICONNECTED PLANE GRAPHS ON O(n²) GRIDS, CONSTRAINED POINT-SET EMBEDDABILITY OF PLANAR GRAPHS, Succinct Greedy Graph Drawing in the Hyperbolic Plane, An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges, Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints, Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three, Four-Connected Spanning Subgraphs of Doughnut Graphs, Cyclic Level Planarity Testing and Embedding, Representation of Planar Hypergraphs by Contacts of Triangles, Drawing Planar Graphs with Reduced Height, Drawing graphs as spanners, Unnamed Item, Proportional Contact Representations of Planar Graphs, Triangulating Planar Graphs While Keeping the Pathwidth Small, A Simple Criterion for Nodal 3-connectivity in Planar Graphs, An Algorithm to Construct Greedy Drawings of Triangulations, Geometry and Generation of a New Graph Planarity Game, Mondshein Sequences (a.k.a. (2,1)-Orders), Unnamed Item, CONVEX GRID DRAWINGS OF FOUR-CONNECTED PLANE GRAPHS, AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING, Morphing Planar Graph Drawings with Bent Edges, A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths, Planar 3-SAT with a clause/variable cycle, Quasi-planar Graphs, Algorithms for 1-Planar Graphs, Right Angle Crossing Drawings of Graphs, An effective crossing minimisation heuristic based on star insertion, Plane 3-Trees: Embeddability and Approximation, A Tipping Point for the Planarity of Small and Medium Sized Graphs, Decision Trees for Geometric Models, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, Intersection graphs of L-shapes and segments in the plane, Drawing plane triangulations with few segments, Outer 1-planar graphs, Recognizing and drawing IC-planar graphs, A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs, Decidability of string graphs, A left-first search algorithm for planar graphs, On simultaneous straight-line grid embedding of a planar graph and its dual, Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices, Grid embedding of 4-connected plane graphs, Drawings of planar graphs with few slopes and segments, From Tutte to Floater and Gotsman: on the resolution of planar straight-line drawings and morphs, One-bend drawings of outerplanar graphs inside simple polygons, Limitations on realistic hyperbolic graph drawing, On simultaneous planar graph embeddings, Area requirement of graph drawings with few crossings per edge, Orthogeodesic point-set embedding of trees, Grid representations and the chromatic number, Triangulating planar graphs while minimizing the maximum degree, On a straight-line embedding problem of graphs, Drawing planar graphs using the canonical ordering, On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm, Skyscraper polytopes and realizations of plane triangulations, New results on drawing angle graphs, Area-efficient planar straight-line drawings of outerplanar graphs, Orthogonal cartograms with at most 12 corners per face, Reprint of: ``Grid representations and the chromatic number, Upward planar drawings on the standing and the rolling cylinders, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Acyclic coloring with few division vertices, Acyclic colorings of graph subdivisions revisited, Rectangular grid drawings of plane graphs, Tree drawings revisited, Dushnik-Miller dimension of contact systems of \(d\)-dimensional boxes, Are there any good digraph width measures?, 4-labelings and grid embeddings of plane quadrangulations, A center transversal theorem for hyperplanes and applications to graph drawing, Small grid embeddings of 3-polytopes, Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs, Arc diagrams, flip distances, and Hamiltonian triangulations, Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs, Point-set embeddings of plane \(3\)-trees, Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges, \(\mathsf{T}\)-shape visibility representations of 1-planar graphs, A note on Schnyder's theorem, Approximate proximity drawings, Drawing trees in a streaming model, Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators, On the edge-length ratio of planar graphs, A note on universal point sets for planar graphs, Homotopy height, grid-major height and graph-drawing height, Graph stories in small area, Pointed drawings of planar graphs, Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, A heuristic approach towards drawings of graphs with high crossing resolution, Counting polygon triangulations is hard, Straight line embeddings of rooted star forests in the plane, Grid drawings of graphs with constant edge-vertex resolution, Long alternating paths in bicolored point sets, A linear-time algorithm for drawing a planar graph on a grid, On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings, Area requirement and symmetry display of planar upward drawings, Crossing number for graphs with bounded pathwidth, A duality transform for constructing small grid embeddings of 3d polytopes, Small universal point sets for \(k\)-outerplanar graphs, Radial drawings of graphs: geometric constraints and trade-offs, Simultaneous graph embedding with bends and circular arcs, On the number of upward planar orientations of maximal planar graphs, The within-strip discrete unit disk cover problem, Faster approximate diameter and distance oracles in planar graphs, Universal point sets for planar three-trees, On the red/blue spanning tree problem, Small grid drawings of planar graphs with balanced partition, Colored simultaneous geometric embeddings and universal pointsets, Curve-constrained drawings of planar graphs, Balanced vertex-orderings of graphs, Planar minimally rigid graphs and pseudo-triangulations, Green's theorem and isolation in planar graphs, Every collinear set in a planar graph is free, The partial visibility representation extension problem, Open rectangle-of-influence drawings of inner triangulated plane graphs, Minimum-width grid drawings of plane graphs, Grid straight-line embeddings of trees with a minimum number of bends per path, Small area drawings of outerplanar graphs, A simple recognition of maximal planar graphs, Zen puzzle garden is NP-complete, A note on isosceles planar graph drawing, Advances in the theory and practice of graph drawing, Upward straight-line embeddings of directed graphs into point sets, A polynomial bound for untangling geometric planar graphs, Visibility representation of plane graphs via canonical ordering tree, Polychromatic colorings of arbitrary rectangular partitions, Optimal two-sided embeddings of complete binary trees in rectangular grids, On a class of covering problems with variable capacities in wireless networks, Incremental convex planarity testing, A force-directed algorithm that preserves edge-crossing properties, The approximate rectangle of influence drawability problem, Free edge lengths in plane graphs, Planarity-preserving clustering and embedding for large planar graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:804582&oldid=12739448"