Embeddability of arrangements of pseudocircles and graphs on surfaces

DOI10.1007/S00454-019-00126-6MaRDI QIDQ2197691zbMATH OpenOpenAlexWikidataFDO

Authors Éric Colin de Verdière, Carolina Medina, Edgardo Roldán-Pensado, Gelasio Salazar

Publication date 1 September 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

arrangements of graphsarrangements of pseudocirclesgraph embeddingsgraphs on surfaces

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Computational aspects related to convexity (52B55) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Relations of low-dimensional topology with graph theory (57M15) Embeddings and immersions in topological manifolds (57N35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A pseudocircle is a simple closed curve on some surface; an arrangement of pseudocircles is a collection of pseudocircles that pairwise intersect in exactly two points, at which they cross. Ortner proved that an arrangement of pseudocircles is embeddable into the sphere if and only if all of its subarrangements of size at most four are embeddable into the sphere, and asked if an analogous result holds for embeddability into orientable surfaces of higher genus. We answer this question positively: An arrangement of pseudocircles is embeddable into an orientable surface of genus~$g$ if and only if all of its subarrangements of size at most $4g+4$ are. Moreover, this bound is tight. We actually have similar results for a much general notion of arrangement, which we call an emph{arrangement of graphs}.

Recommendations

• Embeddability of arrangements of pseudocircles into the sphere
• On the combinatorial structure of arrangements of oriented pseudocircles
• Arrangements of pseudocircles: on circularizability
• Arrangements of pseudocircles and circles
• Arrangements of pseudocircles: on circularizability

Cites work

• A note on convex realizability of arrangements of pseudocircles
• An arrangement of pseudocircles not realizable with circles
• Arrangements of arcs and pseudocircles
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• Arrangements of pseudocircles and circles
• Arrangements of pseudocircles: triangles and drawings
• Embeddability of arrangements of pseudocircles into the sphere
• Embeddings of graphs with no short noncontractible cycles
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Forcing subarrangements in complete arrangements of pseudocircles
• Graphs on surfaces
• scientific article; zbMATH DE number 3394958 (Why is no real title available?)
• Lenses in arrangements of pseudo-circles and their applications
• On arrangements of Jordan arcs with three intersections per pair
• On the combinatorial structure of arrangements of oriented pseudocircles

Cited in

(3)

• Embeddability of arrangements of pseudocircles into the sphere
• Checkerboard embeddings of *-graphs into nonorientable surfaces
• Oriented matroids and complete-graph embeddings on surfaces

This page was built for publication: Embeddability of arrangements of pseudocircles and graphs on surfaces

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