Bounded Embeddings of Graphs in the Plane

DOI10.1007/978-3-319-44543-4_3MaRDI QIDQ2819488zbMATH OpenOpenAlexFDO

Authors Radoslav Fulek

Publication date 29 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.07144

zbMATH Keywords

PQ-treealgebraic crossing numberc-planaritygraph planarity testingweakly simple embedding

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: A drawing in the plane ($mathbb{R}^2$) of a graph $G=(V,E)$ equipped with a function $gamma:VightarrowmathbbN$ is emph{$x$-bounded} if (i) $x(u)<x(v)$ whenever $gamma(u)<gamma(v)$ and (ii) $gamma(u)leqgamma(w)leqgamma(v)$, where $uvinE$ and $gamma(u)leqgamma(v)$, whenever $x(w)inx(uv)$, where $x(.)$ denotes the projection to the $x$-axis. We prove a characterization of isotopy classes of graph embeddings in the plane containing an $x$-bounded embedding. Then we present an efficient algorithm, that relies on our result, for testing the existence of an $x$-bounded embedding if the given graph is a tree or generalized $Theta$-graph. This partially answers a question raised recently by Angelini et al. and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable if each connected component of the underlying abstract graph is a tree.

Recommendations

• Bounded complete embedding graphs
• Graphs embedded in the plane with a bounded number of accumulation points
• Constrained Point-Set Embeddability of Planar Graphs
• Constrained point-set embeddability of planar graphs
• scientific article; zbMATH DE number 1500196
• Plane embeddings of planar graph metrics
• Plane embeddings of planar graph metrics
• scientific article; zbMATH DE number 3968606
• Graph Drawing
• Planar Embeddings of Graphs with Specified Edge Lengths

Cites work

• scientific article; zbMATH DE number 1974122 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Bounds for generalized thrackles
• C-Planarity of C-Connected Clustered Graphs
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• Clustered planarity: small clusters in cycles and Eulerian graphs
• Clustering Cycles into Cycles of Clusters
• Detecting weakly simple polygons
• Eliminating Tverberg points. I. An analogue of the Whitney trick
• Graph Drawing
• Graph Drawing
• Hanani-Tutte, monotone drawings, and level-planarity
• Hierarchical planarity testing algorithms
• Incremental convex planarity testing
• Lectures on Polytopes
• On embedding a cycle in a plane graph
• On simultaneous planar graph embeddings
• On the computational complexity of upward and rectilinear planarity testing
• PC trees and circular-ones arrangements.
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Strip planarity testing
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Total Ordering Problem
• Toward a theory of planarity: Hanani-Tutte and planarity variants
• Towards the Hanani-Tutte theorem for clustered graphs
• Upward drawings of triconnected digraphs.
• Windrose planarity: embedding graphs with direction-constrained edges

Cited in

(16)

• Plane embeddings of planar graph metrics
• ON BOUNDS FOR BALANCED EMBEDDING DEGREE
• Boolean approach to planar embeddings of a graph
• Atomic Embeddability, Clustered Planarity, and Thickenability
• EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
• Bounding the number of embeddings of 5-connected projective-planar graphs
• Stability of intersections of graphs in the plane and the van Kampen obstruction
• Kinetic and Stationary Point-Set Embeddability for Plane Graphs
• Beyond Clustered Planar Graphs
• Hanani-Tutte for Radial Planarity II
• Bounded complete embedding graphs
• Metric graphs elastically embeddable in the plane
• Graphs embedded in the plane with a bounded number of accumulation points
• General theoretical results on rectilinear embeddability of graphs
• Clin d'oeil on \(L_1\)-embeddable planar graphs
• Embedding k-Outerplanar Graphs into l1

This page was built for publication: Bounded Embeddings of Graphs in the Plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819488)