Wyniki wyszukiwania - BazTech

1

Planar packing of cycles and unicyclic graphs

Gorlich A.

Demonstratio Mathematica

|

2009

|

Vol. 42, nr 4

673-679

EN

We say that a graph G is packable into a complete graph Kn if there are two edge-disjoint subgraphs of Kn both isomorphic to G. It is equivalent to the existence of a permutation a of a vertex set in G such that if an edge xy belongs to E(G), then a(x)cr(y) does not belong to E(G). In 2002 Garcia et al. have shown that a non-star tree T is planary packable into a complete graph Kn. In this paper we show that for any packable cycle Cn except of the case n = 5 and n=7 there exists a planar packing into Kn. We also generalize this result to certain classes of unicyclic graphs.

2

Matrix representation and the analysis of shapes of roofs

Koźniewski E.

Journal Biuletyn of Polish Society for Geometry and Engineering Graphics

|

2005

|

Vol. 15

9--19

EN

The paper is the supplement of a series of articles devoted to geometry of roofs. Regular roofs generated by k-connected generalized polygon can treated as geometrical configurations in the form((2V+2(K−2))3, (3V+3(K−2))2) and described by means incidence or adjacence matrices. After all, such represention results from the natural graph-theoretical characterization of roofs described in previous sections. so, a regular roof can be described as An incidence matrix mutually related to vertices ↔edges, and as ad-Jacency matrix mutually related to vertices ↔hipped roof ends (in graph-theoretical interpretation for planar graphs:vertices ↔Regions). In order to built all topological types of roofs every case of the adjacency matrix satisfying the condition (10) Has to be studied. Adjacency matrices are already rare matrices for V=6. Therefore such a combinatorical way should be too complicated to be used here. The way leading through algebraic-geometrical analysis roposed in papers [5,6] seems to be more familiar and simple. In paper [6] the analysis of the existence of topological types Of Roofs only for V=8HAS been made. Here we complete the analysis for the remaining numbers V=3,4,5,6,7 of sides of the base of investigated roofs. Key words: geometry of roofs, planar graph, Euler theorem for roofs, equations of roof, straight skeleton.

PL

Praca stanowi uzupełnienie cyklu artykułów poświęconych geometrii dachów. Dachy regularne, generowane przez k-spójne wielokąty uogólnione mogą być traktowane jako konfiguracje geometryczne postaci ((2v+2(k−2))3, (3v+3(k−2))2) i opisywane za pomocą macierzy incydencji lub adjacencji. Reprezentacja taka wynika z naturalnej, grafowej, charakteryzacji dachów. Ale wówczas, w celu opisania wszystkich topologicznych typów, każdy przypadek macierzy adjacencji, spełniający opisany w pracy warunek, musiałby być rozpatrzony. Ponieważ macierze adjacencji są rzadkie (już dla v=6), ich analiza kombinatoryczna, w przypadkach v=6, 7, 8, wymagałaby rozpatrzenia bardzo dużej liczby przypadków. Pozostaje więc zdecydowanie prostsza droga algebraiczno-geometryczna oparta na własnościach grafów dachów. W artykule przeprowadzono analizę kształtów dachów dla v=3, 4, 5, 6, 7 uzupełniając tym samym treść cyklu pierwszych prac na ten temat.

3

Algorithm for listing the regions of a planar graph

Stemposz E., Rutkowski A.

Image Processing & Communications

|

1998

|

Vol. 4, no 3-4

13-26

EN

In this paper we present an algorithm enumerating all regions (external and inner) of a connected undirected simple planar graph. The main idea for the algorithm is a special travel on graph edges. Since the most time consuming operation we use is sorting of n-element set, the computational complexity of our method is O(nlgn).