Visibility representations of toroidal and Klein-bottle graphs

DOI10.1007/978-3-031-22203-0_29MaRDI QIDQ6172216zbMATH OpenFDO

Authors Therese Biedl

Publication date 16 August 2023

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

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

Mathematics Subject Classification ID

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

Abstract: In this paper, we study visibility representations of graphs that are embedded on a torus or a Klein bottle. Mohar and Rosenstiehl showed that any toroidal graph has a visibility representation on a flat torus bounded by a parallelogram, but left open the question whether one can assume a rectangular flat torus, i.e., a flat torus bounded by a rectangle. Independently the same question was asked by Tamassia and Tollis. We answer this question in the positive. With the same technique, we can also show that any graph embedded on a Klein bottle has a visibility representation on the rectangular flat Klein bottle.

Cites work

• A better heuristic for orthogonal graph drawings
• A note on rectilinear and polar visibility graphs
• A unified approach to visibility representations of planar graphs
• A Visibility Representation for Graphs in Three Dimensions
• Bar k-Visibility Graphs
• Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cyclinder and torus
• Computing an st-numbering
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Graph theory
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 739017 (Why is no real title available?)
• scientific article; zbMATH DE number 2080113 (Why is no real title available?)
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• On the independence ratio of a graph
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Representations of Graphs on a Cylinder
• Representing a planar graph by vertical lines joining different levels
• Tesselation and visibility representations of maps on the torus
• The max clique problem in classes of string-graphs
• The Vertex-Disjoint Menger Problem in Planar Graphs

This page was built for publication: Visibility representations of toroidal and Klein-bottle graphs

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