you're reading...

SACT Talk: Shrinking the Search Space of Clustered Planarity

Time: 11am Friday, 27th July, 2012
Location: SIT 124 Boardroom
Speaker: Karsten Klein, University of Sydney

A clustered graph is a graph augmented with a hierarchical
inclusion structure over its vertices, and arises very naturally in
multiple application areas. While it is long known that
planarity—i.e., drawability without edge crossings—of graphs can be
tested in polynomial (linear) time, the complexity for the clustered
case is still unknown.

We present a new graph theoretic reduction which allows us to
considerably shrink the combinatorial search space, which is of benefit
for all enumeration-type algorithms. Based thereon, we give new classes
of polynomially testable graphs and a practically efficient
exact planarity test for general clustered graphs based on an integer
linear program.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: