An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.
Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.
It was known that planar graphs have the diameter-treewidth property: there is a function f(D) such that any planar graph with diameter D has treewidth at most f(D). (Actually, f(D)=O(D).) We characterize the other minor-closed families with this property: F has the diameter-treewidth property if and only if there is a graph G, formed by adding a vertex to a planar graph, that is not in F. Families with the diameter-treewidth property include bounded-genus graphs (for which again f(D)=O(D)) and K3,a-free graphs. As a consequence, various efficient planar subgraph isomorphism and approximation algorithms can be extended to these families. Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version.
We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.
Describes a graph drawing technique combining ideas of confluent drawing with Sugiyama-style layered drawing. Uses a reduction to graph coloring to find and visualize sets of bicliques in each layer.
Journals -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.