János Pach
Drawing planar graphs of bounded degree with few slopes.
Wed, 09/08/2010 - 15:02 — SomNambulAuthors: János Pach, Dömötör Pálvölgyi, Balázs Keszegh
Subjects: Combinatorics
AbstractWe settle a problem of Dujmovi\'c, Eppstein, Suderman, and Wood by showing
that there exists a function $f$ with the property that every planar graph $G$
with maximum degree $d$ admits a drawing with noncrossing straight-line edges,
using at most $f(d)$ different slopes. If we allow the edges to be represented
by polygonal paths with {\em one} bend, then $2d$ slopes suffice. Allowing {\em
two} bends per edge, every planar graph with maximum degree $d\ge 3$ can be
drawn using segments of at most $\lceil d/2\rceil$ different slopes.Opaque sets.
Wed, 06/23/2010 - 15:02 — SomNambulAuthors: Adrian Dumitrescu, János Pach, Minghui Jiang
Subjects: Computational Geometry
AbstractThe problem of finding ``small'' sets that meet every straight-line which
intersects a given convex region was initiated by Mazurkiewicz in 1916. We call
such a set an {\em opaque set} or a {\em barrier} for that region. We consider
the problem of computing the shortest barrier for a given convex polygon with
$n$ vertices. For general barriers, we present a simple $O(n)$ time
approximation algorithm with ratio $\frac{1}{2}+ \frac{2
+\sqrt{2}}{\pi}=1.5867\ldots$.Minimum clique partition in unit disk graphs.
Thu, 09/10/2009 - 10:12 — SomNambulAuthors: Adrian Dumitrescu, János Pach
Subjects: Computational Geometry
AbstractThe minimum clique partition (MCP) problem is that of partitioning the vertex
set of a given graph into a minimum number of cliques. Given $n$ points in the
plane, the corresponding unit disk graph (UDG) has these points as vertices,
and edges connecting points at distance at most~1. MCP in unit disk graphs is
known to be NP-hard and several constant factor approximations are known,
including a recent PTAS. We present two improved approximation algorithms for
minimum clique partition in unit disk graphs:
User login
