Topological Drawings of Complete Bipartite Graphs

DOI10.1007/978-3-319-50106-2_34MaRDI QIDQ2961537zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Stefan Felsner

Publication date 21 February 2017

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

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. Topological drawings of complete graphs and of complete bipartite graphs have been studied extensively in the context of crossing number problems. We consider a natural class of simple topological drawings of complete bipartite graphs, in which we require that one side of the vertex set bipartition lies on the outer boundary of the drawing. We investigate the combinatorics of such drawings. For this purpose, we define combinatorial encodings of the drawings by enumerating the distinct drawings of subgraphs isomorphic to $K_{2,2}$ and $K_{3,2}$, and investigate the constraints they must satisfy. We prove that a drawing of $K_{k,n}$ exists if and only if some simple local conditions are satisfied by the encodings. This directly yields a polynomial-time algorithm for deciding the existence of such a drawing given the encoding. We show the encoding is equivalent to specifying which pairs of edges cross, yielding a similar polynomial-time algorithm for the realizability of abstract topological graphs. We also completely characterize and enumerate such drawings of $K_{k,n}$ in which the order of the edges around each vertex is the same for vertices on the same side of the bipartition. Finally, we investigate drawings of $K_{k,n}$ using straight lines and pseudolines, and consider the complexity of the corresponding realizability problems.

Recommendations

• scientific article; zbMATH DE number 7030516
• scientific article; zbMATH DE number 2061146
• On drawing regular bipartite graphs
• Book drawings of complete bipartite graphs
• Two-layer drawings of bipartite graphs
• Bipartite graphs, upward drawings, and planarity
• scientific article; zbMATH DE number 6611773
• Convex drawings of the complete graph: topology meets geometry
• On plane subgraphs of complete topological drawings
• Drawings of complete graphs in the projective plane

Cites work

• scientific article; zbMATH DE number 4142090 (Why is no real title available?)
• How many ways can one draw a graph?
• Noncrossing Subgraphs in Topological Layouts
• On a problem of P. Turan concerning graphs
• On the Number of Crossings in a Complete Graph
• Simple realizability of complete abstract topological graphs in P
• Simple realizability of complete abstract topological graphs simplified
• The 2-page crossing number of \(K_{n}\)
• Topological Drawings of Complete Bipartite Graphs
• Zarankiewicz's conjecture is finite for each fixed \(m\)

Cited in

(8)

• Topological Drawings of Complete Bipartite Graphs
• Bishellable drawings of K_n
• scientific article; zbMATH DE number 2061146 (Why is no real title available?)
• Drawing Bipartite Graphs on Two Parallel Convex Curves
• Mutual witness Gabriel drawings of complete bipartite graphs
• scientific article; zbMATH DE number 7030516 (Why is no real title available?)
• Drawing Bipartite Graphs on Two Curves
• The topological drawing of a graph: construction methods

This page was built for publication: Topological Drawings of Complete Bipartite Graphs

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