From: "Andreas Björklund" <oldmoose@algonet.se>
Subject: Re: Applications for planar graphs ?
Date: Wed, 9 Feb 2000 12:39:52 +0100
Newsgroups: sci.math
Summary: [missing]

Christoph Dornheim skrev i meddelandet
<38A12BF6.A477205F@informatik.uni-freiburg.de>...
>Hello,
>
>since I am concerned with planar graphs and planarity algorithms, I
>wonder if there are any other applications for planarity algorithms than
>just
>drawing a given graph without crossings in order to visualize the graph
>nicely.
>
>Does anyone know about real applications different from graph
>visualization, e.g. layout design for electric circuits etc. ?
>
>Thanks in advance for any hint,
>
>Christoph Dornheim
>

Many graph optimization problems have fast algorithms for planar graphs, but
are NP-complete for sparse graphs in general. Therefore, I believe it is of
great interest if planarity can be settled fast.
Regards,
Andreas