Bitonic st-orderings of biconnected planar graphs

Gronemann, Martin (2014) Bitonic st-orderings of biconnected planar graphs.
Published In: Graph Drawing: 22nd International Symposium, GD 2014, Lecture Notes in Computer Science. 8871 Springer 2014, pp. 162-173.


Vertex orderings play an important role in the design of graph drawing algorithms. Compared to canonical orderings, st-orderings lack a certain property that is required by many drawing methods. In this paper, we propose a new type of st-ordering for biconnected planar graphs that relates the ordering to the embedding. We describe a linear-time algorithm to obtain such an ordering and demonstrate its capabilities with two applications.

Download: [img] PDF - Preprinted Version
Download (530kB)
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: No citation data.
Uncontrolled Keywords:
  • 68-XX Computer science > 68Wxx Algorithms

  • Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    Depositing User: Martin Gronemann
    Date Deposited: 03 Sep 2014 12:31
    Last Modified: 24 Nov 2015 09:32