Search

Let G = ( V , E ) and G ′ = ( V ′ , E ′ ) be two graphs. A k-inverse-adjacency-preserving mapping ρ from G to G ′ is a one-to-many and onto mapping from V to V ′ satisfying the following: (1) Each vertex v ∈ V in G is mapped to a non-empty subset ρ ( v ) ⊂ V ′ in G ′ , the cardinality of ρ ( v ) is at most k ; (2) if u ≠ v , then ρ ( u ) ∩ ρ ( v ) = ∅ ; and (3) for any u ′ ∈ ρ ( u ) and v ′ ∈ ρ ( v ) , if ( u ′ , v ′ ) ∈ E ′ , then ( u , v ) ∈ E . A vertex u ′ in ρ ( u ) is called a virtual location for u . Let ρ be a k -inverse-adjacency-preserving-mapping ( k -IAPM for short) from G to G ′ . Let δ be a greedy drawing of G ′ into a metric space M . Consider a message from u to be delivered to v in G . Using the k -IAPM ρ from G to G ′ , intuitively, one can treat the message to be routed as if it were from one virtual location u ′ for u to one virtual location v ′ for v , except that all the virtual locations of a vertex u were identified with each other (which can be thought as instantaneously synchronized mirror sites for a particular website, for example). Then a routing path P ′ can be computed from u ′ to v ′ while identifying all virtual locations for any vertex in G . Since ρ inversely preserves adjacency from G ′ to G , such a routing path P ′ corresponds to exactly one routing path P in G , which connects u to v . In this paper, we formalize the above intuition into a concept which we call k -greedy routing algorithm for a graph G with n vertices, where k refers to the maximum number of virtual locations any vertex of G can have. Using this concept, the result presented in [18] can be rephrased as a 3-greedy routing algorithm for 3-connected plane graphs, where the virtual coordinates used are from 1 to 2 n − 2 . In this paper, we present a 2-greedy routing algorithm for 3-connected plane graphs, where each vertex uses at least one but at most two virtual locations numbered from 1 to 2 n − 1 . For the special case of plane triangulations (in a plane triangulation, every face is a triangle, including the exterior face), the numbers used are further reduced to from 1 to ⌊ 5 n + 1 3 ⌋ . Hence, there are at least ⌈ n − 1 3 ⌉ vertices that use only one virtual location. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we generalize the greedy routing concept to use semi-metric spaces. We prove that any connected -vertex tree admits a greedy embedding, onto an appropriate semi-metric space such that (1) each vertex of the tree is represented by virtual coordinates (where the numbers are from to ); and (2) using an appropriate distance definition, the unique simple path between any two vertices in is always a distance decreasing path between the two vertices. Applying the result to an arbitrary connected graph , such a greedy embedding of any of its spanning tree onto a semi-metric space becomes a greedy embedding of onto the same semi-metric space. In particular, for 3-connected plane graphs, we prove that, for a 3-connected plane graph , there is a greedy embedding of such that: (1) the greedy embedding can be obtained in linear time; (2) each vertex can be represented by at most virtual coordinates from to ; and (3) the distance between two vertices can be computed in constant time. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in bits. [Copyright &y& Elsevier]

Abstract: In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs. [Copyright &y& Elsevier]

Abstract: A (weak) closed rectangle-of-influence (RI for short) drawing is a straight-line planar grid drawing in which there is no other vertex inside or on the boundary of the axis parallel rectangle defined by the two end vertices of any edge. Biedl et al. (1999) showed that a plane graph G has a closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a closed RI drawing in an grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved (Biedl et al., 1999 ). Without loss of generality, we investigate maximal plane graphs admitting closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations (Fusy, 2009 ). In this paper, we present a linear time algorithm that computes closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a closed RI drawing with size at most ; and for a random irreducible triangulation, the expected grid size of the drawing is . We then prove that for arbitrary , there is an n-vertex irreducible triangulation, such that any of its closed RI drawing requires a grid of size . Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in Biedl et al. (1999) negatively. [ABSTRACT FROM AUTHOR]

Abstract: An -orientation or bipolar orientation of a 2-connected graph is an orientation of its edges to generate a directed acyclic graph with a single source and a single sink . Given a plane graph and two exterior vertices and , the problem of finding an optimum -orientation, i.e., an -orientation in which the length of a longest -path is minimized, was first proposed indirectly by Rosenstiehl and Tarjan in and then later directly by He and Kao in . In this paper, we prove that, given a 2-connected plane graph , two exterior vertices , , and a positive integer , the decision problem of whether has an -orientation, where the maximum length of an -path is , is NP-Complete. This solves a long standing open problem on the complexity of optimum -orientations for plane graphs. As a by-product, we prove that the NP-Completeness result holds for planar graphs as well. [Copyright &y& Elsevier]