Bounded Embeddings of Graphs in the Plane

DOI10.1007/978-3-319-44543-4_3zbMATH Open1478.68235arXiv1610.07144OpenAlexW2534301164MaRDI QIDQ2819488FDOQ2819488

Authors: Radoslav Fulek 

Publication date: 29 September 2016

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

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.

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

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

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)

Cites Work

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

Cited In (16)

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

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)