Prev: THE ECHO OF LIFE!
Next: solutions manual
From: bleuprint on 1 Aug 2010 03:18
In 1992 De Ying Li wrote an article with this title, unfortunately it's not on the internet.
It's easy to derive a good sequence from a drawing, but given a sequence when is it a good one? I'm especially interested about the numerical conditions of such sequences (without trying to draw it).
Where can I find some internet site on this?
Thanks in advance.
bleuprint

PS:"maximal outerplanar graphs" are also called "triangulated planar polygons" or "maximal planar polygons" .
From: Gerry Myerson on 1 Aug 2010 19:33
In article
<1055719310.36884.1280661525786.JavaMail.root(a)gallium.mathforum.org>,
bleuprint <patrick.labarque(a)base.be> wrote:

> In 1992 De Ying Li wrote an article with this title, unfortunately it's not
> on the internet.

Moreover, it's written in Chinese.

I don't know whether you'll find the review of any help:

This paper gives a reduction procedure from a sequence $\pi$ to a
sequence $\pi_1$ such that the number of positive entries of $\pi_1$ is
2 less than that of $\pi$ and $\pi$ is the degree sequence of a
potentially maximal outplanar graph if and only if so is $\pi_1$. When
the procedure is carried down to a sequence with no more than 7
positive entries, a complete characterization is established to finish
the task.

Also, it may or may not help to know that the Li paper is in
the references of
MR2419516 (2009c:05053)

Bose, Prosenjit(3-CARL-SC); Dujmovi?, Vida(3-CARL-SC); Krizanc,
Danny(1-WESL-C); Langerman, Stefan(B-ULB-IF); Morin, Pat(3-CARL-SC);
Wood, David R.(E-UPB-A2); Wuhrer, Stefanie(3-CARL-SC)

A characterization of the degree sequences of 2-trees. (English summary)

J. Graph Theory 58 (2008), no. 3, 191--209.

Another paper that might or might not be of any use is

MR2321019 (2008c:05122) Garg, Ashim; Rusu,
Adrian Area-efficient planar straight-line drawings of outerplanar
graphs.
Discrete Appl. Math. 155 (2007), no. 9, 1116--1140.

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: bleuprint on 3 Aug 2010 12:34
Gerry, thanks very much for your answer

> Moreover, it's written in Chinese.
That's indeed a problem

The 1st paper you mentioned:
> "A characterization of the degree sequences of 2-trees"
is precisaly the one where I found the title of the article I mentioned.See: http://www.siam.org/proceedings/analco/2007/anl07_025pbose.pdf

The 2nd paper you mentioned neither has an answer to the problem I'm looking for:

Suppose we are given an ordered(*) triangle-degree(**) sequence.
How can we find out if it's a good one.
One way is the following (illustrated with a good example for 6 vertices):
213213 ordered triangle-degree sequence
subtract 1 from a vertex with degree 1 and also from its two neighbours different from 0, then we get:
102213
again subtract 1 from a vertex... then we get:
102102
again subtract 1 from a vertex... then we get:
101001
again subtract 1 from a vertex... then we get:
000000
If we can obtain in this way all zero's, then we have a good triangle-degree sequence.
a) Is this so?
b) If so, for a big number of vertices this greedy algorithm becomes very tedious. Is there a more direct way to decide if such sequence is a good one?
Patrick

(*) "ordered" means: in clockwise (or counterclockwise order)
(**) Here the triangle-degree n means: the number of inner triangular faces adjacent to a vertex. In most papers the degree of a vertex means: the number of edges adjacent to a vertex (=n+1). For a maximal outerplanar graph sometimes it's the number of "diagonals" adjacent to a vertex (=n-1).
 | 
Pages: 1
Prev: THE ECHO OF LIFE!
Next: solutions manual