Get an In-Depth Understanding of Graph Drawing Techniques, Algorithms, Software, and
Applications The Handbook of Graph Drawing and Visualization provides a broad, up-to …

The on-line planarity-testing problem consists of performing the following operations on a
planar graph G:(i) testing if a new edge can be added to G so that the resulting graph is itself …

In this paper we present near-optimal bounds for fullydynamic graph connectivity which is
the most basic nontrivial fully-dynamic graph problem. Connectivity queries are supported in …

This paper introduces a novel parallel data structure called the recursive star-tree (denoted
“^*-tree”). For its definition a generalization of the * functional is used (where for a function …

A digraph is upward planar if it has a planar drawing such that all the edges are monotone
with respect to the vertical direction. Testing upward planarity and constructing upward …

Motivated by an application to unstructured multigrid calculations, we consider the problem
of asymptotically minimizing the size of dominating sets in triangulated planar graphs …

Several data presentation problems involve drawing graphs so that they are easy to read
and understand. Examples include circuit schematics and diagrams for information systems …

Graph isomorphism is the prime example of a computational problem with a wide difference
between the best known lower and upper bounds on its complexity. There is a significant …

This report deals with a parallel algorithmic technique that has proved to be very useful in
the design of e cient parallel algorithms for several problems on undirected graphs. We …

Parallel algorithms, ie computer operations designed to be performed independently, have
recently increased in importance. Because today's computer applications require more …