scientific article; zbMATH DE number 2123122
Planar graph drawing is a central topic in graph drawing having many applications in information visualization, VLSI design and CAD. This book, written by two well-known experts in graph drawing and theory of planar graphs, is a monograph which nicely covers many aspects of this field and is suitable for use in advanced undergraduate and graduate level courses. It connects fundamental graph-theoretic results with algorithmic aspects. After some introductory chapters, it presents in Chapter 4 straight line drawings of planar graphs on integer grids, and in particular the famous results by de Fraysseix et al. as well as by Schnyder. Then, in Chapter 5, the focus is on convex drawings and the results of Tutte, Thomassen and Chiba et al. as well as recent results on convex grid drawings. Chapter 6 deals with rectangular drawings and results by Miura et al. as well as by Thomassen. Chapter 7 deals with box-rectangular drawings, characterizes plane graphs having a box-rectangular drawing and gives a linear time algorithm for finding such a drawing. Chapter 8 deals with orthogonal drawings of plane graphs, and in particular presents the results by Tamassia for solving the problem of finding a bend-minimum orthogonal drawing by reducing the problem to network flow. Chapter 9 deals with octagonal drawings of plane graphs with prescribed face areas and again contains a linear time algorithm for finding such drawings. Appendix A presents planarity testing and embedding algorithms.
- Drawing slicing graphs with face areas
- Open rectangle-of-influence drawings of inner triangulated plane graphs
- An algorithm for constructing star-shaped drawings of plane graphs
- Orthogonal layout with optimal face complexity
- HV-planarity: algorithms and complexity
- The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs
- On triangle cover contact graphs
- Realizability of graphs as triangle cover contact graphs
- The complexity of drawing a graph in a polygonal region
- Construction of a topological drawing of the most planar subgraph of the non-planar graph
- Acyclic colorings of graph subdivisions revisited
- Orthogonal planarity testing of bounded treewidth graphs
- Force-directed layout of order diagrams using dimensional reduction
- Star colouring of bounded degree graphs and regular graphs
- Convex grid drawings of planar graphs with constant edge-vertex resolution
- Grid drawings of graphs with constant edge-vertex resolution
- Re-embedding a 1-plane graph for a straight-line drawing in linear time
- Computing upward topological book embeddings of upward planar digraphs
- On orthogonally convex drawings of plane graphs
- Minimum-segment convex drawings of 3-connected cubic plane graphs
- An annotated bibliography on 1-planarity
- A linear-time algorithm for star-shaped drawings of planar graphs with the minimum number of concave corners
- Parameterized complexity of graph planarity with restricted cyclic orders
- Planar drawing algorithms of survivable telecommunication networks
- Drawing planar graphs
- Realizability of Graphs as Triangle Cover Contact Graphs
- Circular right-angle crossing drawings in linear time
- Minimum-layer drawings of trees (extended abstract)
- Consecutive ones property testing: cut or swap
- Handbook of graph drawing and visualization
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- An application of st-numbering to secret key agreement
- Drawing Graphs with Right Angle Crossings
- On some properties of doughnut graphs
- Generating All Triangulations of Plane Graphs (Extended Abstract)
- Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n logn) Area (Extended Abstract)
- Matched Drawability of Graph Pairs and of Graph Triples
- Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints
- Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three
- The topological drawing of a graph: construction methods
- Orthogonal cartograms with at most 12 corners per face
- Polynomial algorithms for open plane graph and subgraph isomorphisms
- Minimum cost star-shaped drawings of plane graphs with a fixed embedding and concave corner constraints
- Pointed drawings of planar graphs
- Minimum Integral Drawings of the Platonic Graphs
- Geometric graphs in the plane lattice
- Beyond planar graphs: introduction
- Algorithms for 1-Planar Graphs
- Crossing Layout in Non-planar Graph Drawings
- On the Edge-Length Ratio of 2-Trees
- On Turn-Regular Orthogonal Representations
- Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
- On turn-regular orthogonal representations
- The complexity of drawing a graph in a polygonal region
- The Enumeration of Spanning Trees in Dual, Bipartite and Reduced Graphs
- On edge-length ratios of partial 2-trees
- Beyond planar graphs. Communications of National Institute of Informatics (NII) Shonan meetings, Shonan, Japan, November 27 -- December 1, 2016
- Recent developments in floorplan representations
- L-shaped point set embeddings of high-degree plane graphs
- Algorithms and Computation
- Untangling planar graphs from a specified vertex position-Hard cases
- Computing Upward Topological Book Embeddings of Upward Planar Digraphs
- Four-Connected Spanning Subgraphs of Doughnut Graphs
- Triangulations with Circular Arcs
- Approximation algorithms for minimizing edge crossings in radial drawings
- Parameterized complexity of graph planarity with restricted cyclic orders
- Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time
- Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
- k-Planar Placement and Packing of Δ-Regular Caterpillars
- 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
- Unit-length rectangular drawings of graphs
- Rectilinear planarity of partial 2-trees
- Relating planar graph drawings to planar satisfiability problems
- Linear-time rectilinear drawings of subdivisions of triconnected cubic planar graphs with orthogonally convex faces
- Rectilinear Planarity of Partial 2-Trees
- Linear-time construction of floor plans for plane triangulations
- An annotated review on graph drawing and its applications
- Sliding column model for t-unit bar visibility representations of graphs
- Convex grid drawings of planar graphs with constant edge-vertex resolution
- \texttt{CelticGraph}: drawing graphs as Celtic knots and links
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
- Unit-length rectangular drawings of graphs
- Efficient enumeration of transversal edge-partitions
- Rectilinear-upward planarity testing of digraphs
- Graphtrials: visual proofs of graph properties
- Rectilinear-upward planarity testing of digraphs
- Small grid drawings of planar graphs with balanced partition
- Linear-time algorithm for generating L-shaped floorplans using canonical ordering technique
- Drawing graphs with right angle crossings
- A census of graph-drawing algorithms based on generalized transversal structures
- Planar bus graphs
- Upward and rectilinear planarity are W[1]-hard parameterized by treewidth
- A walk on the wild side: a shape-first methodology for orthogonal drawings
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Greedy drawings of triangulations
- Good spanning trees in graph drawing
- Point-set embeddings of trees with given partial drawings
- On the obfuscation complexity of planar graphs
- Drawing colored graphs with constrained vertex positions and few bends per edge
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3154374)
