Generation of planar graphs based on their faces

Mohammadreza Jooyandeh (Research School of Computer Science)

CS HDR MONITORING

DATE: 2011-11-28
TIME: 10:00:00 - 10:30:00
LOCATION: CSIT Seminar Room, N101
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
In this talk we describe how k-angulations (planar graphs with faces of size k) can be generated. The algorithm uses the fast algorithm for generating triangulations and quadrangulations and uses two operations in a recursive manner. The generator is based on the canonic al construction path method to avoid isomorphic copies. The families which can be generated with this approach are k-angulations and 2-connected k-angulations. More generally adding another operation we are able to generate all planar graphs with faces of size in a given set.
BIO:
Mohammadreza is a PhD students in the Research School of Computer Science