Approximate Shortest Path Queries on Weighted Polyhedral Surfaces ⋆ (2009)
Lyudmil Aleks, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-rüdiger Sack
Abstract. We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface P consisting of n triangular faces. We present query...
Efficient Computation of Minimum Exposure Paths in a Sensor Network Field (2008)
Abstract. The exposure of a path p is a measure of the likelihood that an object traveling along p is detected by a network of sensors and it is formally defined as an integral over all points x of p...
Force-directed methods for mesh improvement 1 (2007)
We study the design and implementation of algorithms for repositioning the points of a planar triangular mesh in order to improve the shapes of its faces. Our approach is based on a variation of the...
On Drawing a Graph Convexly in the Plane (Extended Abstract) (2007)
H.N. Djidjev, Hristo N. Djidjev
) ? Hristo N. Djidjev Department of Computer Science, Rice University, Hoston, TX 77251, USA Abstract. Let G be a planar graph and H be a subgraph of G. Given any convex drawing of H, we investigate...
Crossing numbers and cutwidths (2007)
The crossing number of a graph G = (V,E), denoted by cr(G), is the smallest number of edge crossings in any drawing of G in the plane. Wee assume that the drawing is good, i.e., incident edges do not...
Approximate shortest path queries on weighted polyhedral surfaces (2006)
Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-rüdiger Sack
We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface P consisting of n triangular faces. We present query...
Force-directed methods for smoothing unstructured triangular and tetrahedral meshes (2000)
We develop and implement new algorithms for smoothing triangular and tetrahedral unstructured meshes. Our approach is based on a variation of the force-directed method used in graph drawing. This...
Computing the girth of a planar graph (2000)
Abstract. The girth of a graph G has been dened as the length of a shortest cycle of G. We design an O(n 5=4 log n) algorithm for nding the girth of an undirected n-vertex planar graph, giving the...
Force-directed methods for smoothing unstructured triangular and tetrahedral meshes (2000)
We develop and implement new algorithms for smoothing triangular and tetrahedral unstructured meshes. Our approach is based on a variation of the force-directed method used in graph drawing. This...
Efficient Algorithms for Shortest Path Queries in Planar Digraphs (1996)
. This paper describes algorithms for answering shortest path queries in digraphs with small separators and, in particular, in planar digraphs. In this version of the problem, one has to preprocess...
Improved Algorithms for Dynamic Shortest Paths (1996)
Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis
We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is...
On Computing Voronoi Diagrams For Sorted Point Sets (1995)
Hristo N. Djidjev, Andrzei Lingas
We show that the Voronoi diagram of a finite sequence of points in the plane which gives sorted order of the points with respect to two perpendicular directions can be computed in linear time. In...
A Linear Algorithm For Finding A Maximal Planar Subgraph (1995)
We construct an optimal linear time algorithm for the maximal planar subgraph problem: given a graph G, find a planar subgraph G 0 of G such that adding to G 0 any edge of G not present in G 0 leads...
Planarization of Graphs Embedded on Surfaces (1995)
Hristo N. Djidjev, Shankar M. Venkatesan
A planarizing set of a graph is a set of edges or vertices whose removal leaves a planar graph. It is shown that, if G is an n-vertex graph of maximum degree d and orientable genus g, then there...
Separators in Graphs with Negative and Multiple Vertex Weights (1994)
Hristo N. Djidjev, John R. Gilbert
A separator theorem for a class of graphs asserts that every graph in the class can be divided approximately in half by removing a set of vertices of specified size. Nontrivial separator theorems...
Partitioning Graphs with Costs and Weights on Vertices: Algorithms and Applications
We prove separator theorems in which the size of the separator is minimized with respect to non-negative vertex costs. We show that for any planar graph G there exists a vertex separator of total...