Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. One consequence is a parallel algorithm to list all subgraphs isomorphic to K3 or K4.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
It was known that planar graphs have O(n) subgraphs isomorphic to K3 or K4. This paper characterizes the subgraphs for which such a linear bound holds: they are exactly the 3-connected planar graphs. Please note that the Tech. Rep. version had a bug (in a supposed generalization of the result to nonplanar graph families) which was corrected in the journal version.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
For any sparse family of graphs, one can list in linear time all complete bipartite subgraphs of a graph in the family. There are O(n) complete bipartite subgraphs of a graph in the family, and the sum of the numbers of vertices in these subgraphs is also O(n).
Nowadays these results can also be interpreted as a form of formal concept analysis. If a set of objects and attributes is sparse (e.g., if it is generated by adding objects and attributes one at a time, where each newly-added object is given O(1) attributes and each newly-added attribute is held by O(1) objects) then the total size of all concepts in its concept lattice is linear, and this lattice may be generated in linear time.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.
(BibTeX -- Citations -- Citations from MIT hypertext bibliography -- CiteSeer (SODA) -- CiteSeer (JGAA))
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 describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.
We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.
(Preprint)
We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.
Graph Theory -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.