共查询到20条相似文献,搜索用时 15 毫秒
1.
Michał Lasoń Piotr Micek Arkadiusz Pawlik Bartosz Walczak 《Discrete and Computational Geometry》2014,52(2):399-415
A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line \(L\) if the intersection of any member with \(L\) is a nonempty segment. It is proved that the intersection graphs of simple families of compact arc-connected sets in the plane pierced by a common line have chromatic number bounded by a function of their clique number. 相似文献
2.
3.
4.
Michael S. Payne Attila Pór Pavel Valtr David R. Wood 《Discrete and Computational Geometry》2012,48(3):669-681
The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71?C93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)??deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most ? collinear vertices has connectivity at least $\frac{n-1}{\ell-1}$ , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that ?=4 we improve this bound to two thirds of the minimum degree. 相似文献
5.
Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph
satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if
affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph. 相似文献
6.
Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph
satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if
affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph. 相似文献
7.
Abstract. We define a natural class of graphs by generalizing prior notions of visibility, allowing the representing regions and sightlines
to be arbitrary. We consider mainly the case of compact connected representing regions, proving two results giving necessary
properties of visibility graphs, and giving some examples of classes of graphs that can be so represented. Finally, we give
some applications of the concept, and we provide potential avenues for future research in the area. 相似文献
8.
Abstract. We define a natural class of graphs by generalizing prior notions of visibility, allowing the representing regions and sightlines
to be arbitrary. We consider mainly the case of compact connected representing regions, proving two results giving necessary
properties of visibility graphs, and giving some examples of classes of graphs that can be so represented. Finally, we give
some applications of the concept, and we provide potential avenues for future research in the area. 相似文献
9.
J��lius Czap Stanislav Jendrol�� Franti?ek Kardo? Jozef Mi?kuf 《Graphs and Combinatorics》2011,27(1):73-85
A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity,
and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We
also present infinite classes of graphs where the equalities are attained. 相似文献
10.
11.
J. Cel 《Geometriae Dedicata》1999,74(2):135-137
Let S be a nonempty set in a real topological linear space L. p S is a point of maximal visibility of S if and only if it admits a neighbourhood N in L such that Sq
Sp for every point q S N, where Sx = { s S : x is visible from s via S }. For S being either open and connected or the closure of its connected interior, it is shown that the kernel of S is the set of all maximal visibility points of S. Planar examples reveal that the topological assumptions on S are necessary. This substantially strengthens a recent result of Toranzos and Forte Cunto. 相似文献
12.
Let E be a compact subset of C. We prove that if E satisfies the following local Markov property: for each polynomial P,
where M, m, s are positive constants independent of P,
and
; then E is L-regular, i.e. regular in the sense of the potential theory. In particular, if
satisfies the global Markov inequality, then E is L-regular. We also prove that if
is an m-perfect set (there exists c > 0 such that, for all
and $r\in (0,1]$,
and
, then E is L-regular. Examples given by Siciak [20] show that the assumption that m < 2 cannot be omitted. 相似文献
13.
Marilyn Breen 《Monatshefte für Mathematik》2000,130(1):1-5
Let , where is an open connected subset of some linear topological space, such that S contains all triangular regions whose (relative) boundaries lie in S. If some finite subset T of S has locally maximal visibility in S, then . Hence S is a finite union of starshaped sets whose kernels are determined by T. An analogous result holds for S open. Moreover, counterexamples show that neither the requirement on triangular regions nor the restriction to a finite set
T can be deleted.
(Received 7 September 1998; in revised form 25 October 1999) 相似文献
14.
Md. Saidur Rahman Shin-ichi Nakano Takao Nishizeki 《Journal of Algorithms in Cognition, Informatics and Logic》2000,37(2):363
In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a linear-time algorithm to find a box-rectangular drawing of G if it exists. 相似文献
15.
Noga Alon Robert Berke Kevin Buchin Maike Buchin Péter Csorba Saswata Shannigrahi Bettina Speckmann Philipp Zumstein 《Discrete and Computational Geometry》2009,42(3):421-442
We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident
to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is
-complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed
(possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes)
for which the corresponding decision problem is in ℘, and for the others it is
-complete.
Research of N. Alon was supported in part by the Israel Science Foundation, by a USA–Israeli BSF grant, and by the Hermann
Minkowski Minerva Center for Geometry at Tel Aviv University.
Research of R. Berke was supported in part by JSPS Global COE program “Computationism as a Foundation for the Sciences.”
Research of K. Buchin and M. Buchin was supported by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS
project no. 642.065.503.
Research of P. Csorba was supported by DIAMANT, an NWO mathematics cluster.
Research of B. Speckmann was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.022.707. 相似文献
16.
Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α
1
, α
2
, . . . ,α
n
be positive real numbers such that α
1
+α
2
+ ⋅ ⋅ ⋅ +α
n
=1 and 0< α
i
≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T
1
, T
2
, . . . ,T
n
so that each T
i
satisfies the following three conditions: (i) area(T
i
)=α
i
× area(S) ; (ii) ℓ (T
i
∩ ∂ (S))= α
i
× ℓ (∂ (S)) ; and (iii) T
i
∩ ∂ (S) consists of exactly one continuous curve. 相似文献
17.
Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α
1
, α
2
, . . . ,α
n
be positive real numbers such that α
1
+α
2
+ ⋅ ⋅ ⋅ +α
n
=1 and 0< α
i
≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T
1
, T
2
, . . . ,T
n
so that each T
i
satisfies the following three conditions: (i) area(T
i
)=α
i
× area(S) ; (ii) ℓ (T
i
∩ ∂ (S))= α
i
× ℓ (∂ (S)) ; and (iii) T
i
∩ ∂ (S) consists of exactly one continuous curve. 相似文献
18.
19.
Geodesic convex sets, Steiner convex sets, and J-convex (alias induced path convex) sets of lexicographic products of graphs are characterized. The geodesic case in particular
rectifies Theorem 3.1 in Canoy and Garces (Graphs Combin 18(4):787–793, 2002). 相似文献