A New Method for Efficiently Generating Planar Graph Visibility Representations

摘要

This research has yielded a new method for generating planar graph visibility representations. A linear-time reference implementation is available from the author based on the edge addition reference implementation that accompanies, A pre-computed si-numbering was found to not be necessary, though the vertex ordering method produces an si-numbering as an output. It would be of theoretical interest to determine whether the notions of visibility representation and st-numbering could be completely decoupled, but first appearances suggest there would be little practical benefit as the sweep algorithm for edge ordering appears to become much more complicated with multiple source vertices. Future work would more easily find ways to compact the drawings via refinement of the algorithm presented in this paper.