A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs

A graph G is 1-planar if it can be embedded in the plane in such a way that each edge crosses at most one other edge. Borodin showed that 1-planar graphs are 6-colorable, but his proof does not lead to a linear-time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-plane graphs (which are 1-planar graphs already embedded in the plane). The main difficulty in the design of our algorithm comes from the fact that the class of 1-planar graphs is not closed under the operation of edge contraction. This difficulty is overcome by a structural lemma that may be useful in other problems on 1-planar graphs. This paper also shows that it is NP-complete to decide whether a given 1-planar graph is 4-colorable. The complexity of the problem of deciding whether a given 1-planar graph is 5-colorable is still unknown.     

A note on total colorings of 1-planar graphs

A 1-planar graph is a graph that can be drawn in the plane such that each edge is crossed by at most one other edge. In this paper we give an upper bound for the total chromatic number for 1-planar graphs with maximum degree at least 10.     

外1-平面图的均匀边染色

图[G]的[s]-均匀边[k]-染色是指用[k]种颜色对图的边进行染色,使得图[G]的每个顶点所关联的任何两种颜色的边的条数至多相差[s]。使得对于每个不小于[k]的整数[t],图[G]都具有[s]-均匀边[t]-染色的最小整数[k]称为图[G]的[s]-均匀边色数阈值。文中证明了外1-平面图的1-均匀边色数阈值最多为5,不含有相邻的3圈的外1-平面图的均匀边色数阈值最多为4,外1-平面图的2-均匀边色数阈值恰好为1。     

On edge colorings of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that every 1-planar graph with maximum degree Δ?10 can be edge-colored with Δ colors.     

外1-平面图的均匀点荫度

图的均匀树[k]-染色是图的一个点[k]-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图[G]具有均匀树[k]-染色的最小整数[k]称为图[G]的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。     

Representing graph families with edge grammars

An edge grammar is a formal mechanism for representing families of related graphs (binary trees, hypercubes, meshes, etc.). Given an edge grammar, larger graphs in the family are derived from simple basis graphs using edge rewriting rules. A drawback to many graph grammars is that they cannot represent some important, highly regular graph families such as the family of shuffle-exchange graphs. Edge grammars, however, exist for all “computable” graph families, and simple edge grammars exist for most regular graph families. In this paper, we define and illustrate edge grammars and analyze them in the context of formal language theory. Our results include hierarchy and decidability properties. Because this work originally was motivated by a need to represent graph families found in parallel computation, the application of edge grammars in this context is also discussed.     

Efficient Orthogonal Drawings of High Degree Graphs

Most of the work that appears in the two-dimensional orthogonal graph drawing literature deals with graphs whose maximum degree is four. In this paper we present an algorithm for orthogonal drawings of simple graphs with degree higher than four. Vertices are represented by rectangular boxes of perimeter less than twice the degree of the vertex. Our algorithm is based on creating groups / pairs of vertices of the graph. The orthogonal drawings produced by our algorithm have area at most (m-1) ( m / 2 +2) . Two important properties of our algorithm are that the drawings exhibit a small total number of bends (less than m ), and that there is at most one bend per edge. Received January 15, 1997; revised February 1, 1998.     

Rainbow graph splitting

Given an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c=2, whereas for c≥3 it is NP-complete even if the graph has maximum degree 2c−1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c−14.     

Efficient algorithms for (3, 1) graphs

In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive a lower bound for the size of a maximum clique in a (3, 1) graph as well as an upper bound for the size of a minimum clique covering. In addition, we show that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected (3, 1) graph and an n⁴-algorithm for finding a minimum coloring in a (3, 1) graph.     

无向哈密顿图的一个充分必要条件及计算公式

哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念。任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通。根据这个充分必要条件,推导出了一个必要条件计算公式。它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图。此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性。     

Maximum gap labelings of graphs

Given a graph, we define a base set to be a set of integers of size equal to the number of vertices in the graph. Given a graph and a base set, a labeling of the graph from the base set is an assignment of distinct integers from the base set to the vertices of the graph. The gap of an edge in a labeled graph is the absolute value of the difference between the labels of its endpoints. The gap of a labeled graph is the sum of the gaps of its edges.The maximum gap graph labeling problem takes as input a graph and a base set and maximizes the gap of the graph over all possible labelings from the base set. We show that this problem is NP-complete even when the base set is restricted to consecutive integers. We also show that this restricted case has polynomial time approximations that achieve a factor of 2/3 for trees, of 1/2 for bipartite graphs, and of 1/4 for general graphs, with a deterministic algorithm, while an expected factor of 1/3 for general graphs is achieved with a randomized algorithm. The case of general base sets is approximated within an expected factor of 1/16 for general graphs with a randomized polynomial time algorithm. We finally give a polynomial time algorithm that solves the maximum gap graph labeling problem for a graph that has bounded degree and bounded treewidth. The maximum graph labeling problem shows connections with the graceful tree conjecture.     

A browser for directed graphs

A general-purpose browser for directed graphs is described. The browser provides operations to examine and edit graphs and to generate a layout for a graph automatically that minimizes edge crossings. Two layout algorithms were implemented. A hierarchical graph layout algorithm was found to be best for directed graphs. The graph browser also has facilities that allow it to be integrated with other applications (e.g. a program browser). These facilities and our experiences building a program call-graph browser are described.     

A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.     

Dolha - an efficient and exact data structure for streaming graphs

A streaming graph is a graph formed by a sequence of incoming edges with time stamps. Unlike the static graphs, the streaming graph is highly dynamic and time-related. Streaming graphs in the real world, which are of the high volume and velocity, can be challenging to the classic graph data structures: data of internet traffic, social network communication, and financial transections, etc. The traditional graph storage models like the adjacency matrix and the adjacency list are no longer sufficient for the large amount data and high frequency updates. And most the streaming graph structures are only supports the specific graph algorithms. Here a new data structure is presented to meet the challenge: a double orthogonal list in hash table (Dolha) as a high speed and high memory efficiency graph structure. Dolha has constant time cost for single edge processing, and near-linear space cost. Moreover, time cost for neighborhood queries in Dolha is linear, which enables it to support most algorithms of graphs without extra cost. A persistent structure based on Dolha is also presented, to handle the sliding window update and time related queries.

     

Algorithms for Graphs Embeddable with Few Crossings per Edge

We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker and Eppstein to a much broader class of graphs. We also prove that for the considered class of graphs, there are balanced separators of size where n is a number of vertices in the graph. On the negative side, we prove that it is intractable to recognize the graphs embeddable in the plane with at most one crossing per edge.     

Error Compensation in Leaf Power Problems

The k-Leaf Power recognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree—the k-leaf root—with leaves one-to-one labeled by the graph vertices and where the leaves have distance at most k iff their corresponding vertices in the graph are connected by an edge. Here we study "error correction" versions of k-Leaf Power recognition—that is, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-Leaf Power problem (the error correction version of 3-Leaf Power) is fixed-parameter tractable with respect to the number of edge modifications or vertex deletions in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf power problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.     

The bicube: an interconnection of two hypercubes

We consider two definitions of the even-dimensional hypercube given in the literature. The labelled graphs obtained by two definitions are not same, but one is isomorphic to the other. By interconnecting two labelled graphs in such a way that each pair of vertices with the same label are joined by an edge, we construct a vertex-symmetric graph with the diameter about half that of a comparable hypercube. We extend the result to a general scheme for interconnecting two hypercubes to produce a network topology called the bicube. We show that the bicube preserves the vertex-symmetry, bipartiteness, hamiltonian and bipancyclic properties of the hypercube, and is highly edge-symmetric.     

On Finding Min-Min Disjoint Paths

The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard and admits no K-approximation for any K>1 in the general case (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006). In this paper, we first show that Bhatia et al.’s NP-hardness proof (Bhatia et al. in J. Comb. Optim. 12:83–96, 2006), a claim of correction to Xu et al.’s proof (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006), for the edge-disjoint Min-Min problem in the general undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in the proof of Bhatia et al. (J. Comb. Optim. 12:83–96, 2006). We then gave a correct proof of NP-hardness of this problem in undirected graphs. Finally we give a polynomial-time algorithm for the vertex disjoint Min-Min problem in planar graphs by showing that the vertex disjoint Min-Min problem is polynomially solvable in st-planar graph G=(V,E) whose corresponding auxiliary graph G(V,E∪{e(st)}) can be embedded into a plane, and a planar graph can be decomposed into several st-planar graphs whose Min-Min paths collectively contain a Min-Min disjoint-path pair between s and t in the original graph G. To the best of our knowledge, these are the first polynomial algorithms for the Min-Min problems in planar graphs.     

On existence of reporter strands in DNA-based graph structures

Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that “preserves the graph structure” and traverses each edge.     

Editing to Eulerian graphs

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations.