论文标题
环形和克莱因瓶图的可见性表示
Visibility Representations of Toroidal and Klein-bottle Graphs
论文作者
论文摘要
在本文中，我们研究了嵌入在圆环或克莱因瓶中的图形的可见性表示。 Mohar和Rosenstiehl表明，任何圆环图都在平行四边形的扁平圆环上具有可见性表示，但请打开一个问题，即是否可以假设一个矩形平坦的圆环，即由矩形界定的平坦圆环。塔玛西亚和托利斯独立提出了同样的问题。我们以积极的态度回答这个问题。使用相同的技术，我们还可以证明，嵌入在克莱因瓶上的任何图都在矩形扁平klein瓶上具有可见性表示。
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.
