共查询到20条相似文献,搜索用时 0 毫秒
1.
Hiroshi Sakamoto 《Journal of Discrete Algorithms》2005,3(2-4):416-430
A linear-time approximation algorithm for the grammar-based compression is presented. This is an optimization problem to minimize the size of a context-free grammar deriving a given string. For each string of length n, the algorithm guarantees approximation ratio without suffix tree construction. 相似文献
2.
3.
We establish several geometric extensions of the Lipton-Tarjan separator theorem for planar graphs. For instance, we show that any collection C of Jordan curves in the plane with a total of m crossings has a partition into three parts C=S∪C1∪C2 such that , , and no element of C1 has a point in common with any element of C2. These results are used to obtain various properties of intersection patterns of geometric objects in the plane. In particular, we prove that if a graph G can be obtained as the intersection graph of n convex sets in the plane and it contains no complete bipartite graph Kt,t as a subgraph, then the number of edges of G cannot exceed ctn, for a suitable constant ct. 相似文献
4.
5.
In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n 5/3(loglogn)1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability. 相似文献
6.
Drawings of planar graphs with few slopes and segments 总被引:1,自引:0,他引:1
Vida Dujmovi David Eppstein Matthew Suderman David R. Wood 《Computational Geometry》2007,38(3):194-212
We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered. 相似文献
7.
8.
9.
On stable cutsets in claw-free graphs and planar graphs 总被引:4,自引:0,他引:4
A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let and (claw) denote the complete (bipartite) graph on 4 and vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a -free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, )-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for -free planar graphs with maximum degree five. 相似文献
10.
《Discrete Mathematics》2019,342(2):339-343
A strong edge-coloring of a graph is a partition of its edge set into induced matchings. Let be a connected planar graph with girth and maximum degree . We show that either is isomorphic to a subgraph of a very special -regular graph with girth , or has a strong edge-coloring using at most colors. 相似文献
11.
The longest path problem is a well-known NP-hard problem and so far it has been solved polynomially only for a few classes of graphs. In this paper, we give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph. 相似文献
12.
13.
It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for all chromatic polynomials. Jackson [A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325-336] discovered that is another maximal zero-free interval for all chromatic polynomials. In this note, we show that is actually a maximal zero-free interval for the chromatic polynomials of bipartite planar graphs. 相似文献
14.
A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχi(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χi(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χi(G)≤Δ+1 if g≥11; (3) χi(G)≤Δ+2 if g≥8. 相似文献
15.
Vojislav Petrovi 《Discrete Mathematics》1996,150(1-3):449-451
We prove that each simple planar graph G whose all faces are quadrilaterals can be decomposed into two disjoint trees Tr and Tb such that V(Tr) = V(G − u) and V(Tb) = V(G − v) for any two non-adjacent vertices u and v of G. 相似文献
16.
In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows. 相似文献
17.
Stefan Felsner 《Discrete Mathematics》2010,310(5):1097-1104
In this paper, we show that the dimension of the adjacency poset of a planar graph is at most 8. From below, we show that there is a planar graph whose adjacency poset has dimension 5. We then show that the dimension of the adjacency poset of an outerplanar graph is at most 5. From below, we show that there is an outerplanar graph whose adjacency poset has dimension 4. We also show that the dimension of the adjacency poset of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poset of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poset of such a graph. 相似文献
18.
19.
《Discrete Mathematics》2022,345(10):113002
We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen from 1974. 相似文献
20.
Improved bounds for acyclic chromatic index of planar graphs 总被引:1,自引:0,他引:1