Planarity and Planar Graphs

Planarity and Planar Graphs

Topic home

Graph Drawing
 Topics
 Tools

Publications:
 By type
 By year

Planarity and Planar Graphs

    Models and algorithms to compute planar drawings of graphs.

    The study of topological and geometric properties of planar graphs is central in Graph Theory and in our group.

    We study the topological and geometric properties of planar graphs from both a combinatorial and an algorithmic point of view.

    • Combinatorics: We are interested in bounds for the area requirements of planar graphs and their sub-classes (see topic "Minimum Size Representations of Graphs"), in determining classes of planar graphs admitting certain proximity representations (see topic "Proximity Drawings"), in determining classes of planar graphs admitting certain simultaneous representations (see topic "Simultaneous Information Visualization").
    • Algorithmics: We are interested in algorithms for obtaining topological and geometric representations of planar graphs and in determining the complexity of certain optimization and decision problems on planar graphs. To cite some examples, our group deals with the c-planarity problem on clustered graphs (see topic "Clustered Graphs"), with efficient algorithms for drawing planar graphs in small area (see topic "Minimum Size Representations of Graphs"), and with the problem of testing whether some planar graphs have a simultaneous representation (see topic "Simultaneous Information Visualization").