Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Topological Drawings of Complete Bipartite Graphs
verfasst von : Jean Cardinal, Stefan Felsner
Erschienen in: Graph Drawing and Network Visualization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. 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 in particular that for complete bipartite graphs of the form \(K_{2,n}\) and \(K_{3,n}\), such an encoding corresponds to a drawing if and only if it obeys consistency conditions on triples and quadruples. In the general case of \(K_{k,n}\) with \(k\ge 2\), we completely characterize and enumerate drawings in which the order of the edges around each vertex is the same for vertices on the same side of the bipartition.