Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

a
p
Visibility Graphs J
Maximum number of edges in a rectangle k-visibility graph
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#1 • 2 Y
This topic is linked to Hartke - Exercise A.
Y by goodbear, Adventure10
Is the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices at most twice the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

Why or why not?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#2 • 1 Y
Y by Adventure10
Consider the two bar $k$-visibility graphs made by
  1. collapsing the rectangles vertically and keeping the vertical line segments, and
  2. collapsing the rectangles horizontally and keeping the horizontal line segments.
The sum of the number of segments in the two bar $k$-visibility graphs is the number of the segments the original rectangle $k$-visibility graph had. Since these all have the same number of vertices, the statement is true.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#3 • 1 Y
Y by Adventure10
goodbear wrote:
Consider the two bar $k$-visibility graphs made by
  1. collapsing the rectangles vertically and keeping the vertical line segments, and
  2. collapsing the rectangles horizontally and keeping the horizontal line segments.
The sum of the number of segments in the two bar $k$-visibility graphs is the number of the segments the original rectangle $k$-visibility graph had. Since these all have the same number of vertices, the statement is true.
This is right. Does anyone see how to get any lower bounds for the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices?

Also, what are upper and lower bounds for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
parityhome
132 posts
#4 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
goodbear wrote:
Consider the two bar $k$-visibility graphs made by
  1. collapsing the rectangles vertically and keeping the vertical line segments, and
  2. collapsing the rectangles horizontally and keeping the horizontal line segments.
The sum of the number of segments in the two bar $k$-visibility graphs is the number of the segments the original rectangle $k$-visibility graph had. Since these all have the same number of vertices, the statement is true.
This is right. Does anyone see how to get any lower bounds for the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices?

Also, what are upper and lower bounds for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?

To clarify, are the segments representing the edges allowed to intersect? Do the rectangles intersect?
This post has been edited 1 time. Last edited by parityhome, Feb 2, 2017, 6:14 AM
Reason: added another clarification question?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#5 • 1 Y
Y by Adventure10
JGeneson wrote:
Does anyone see how to get any lower bounds for the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices?

Also, what are upper and lower bounds for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?

One obvious lower bound for $n>k$ is $n(k+1)-\frac{(k+1)(k+2)}2,$ which comes from putting $d$-dimensional cubes in a row, like so:

Diagram
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#6 • 2 Y
Y by Adventure10, Mango247
parityhome wrote:
To clarify, are the segments representing the edges allowed to intersect? Do the rectangles intersect?
The segments representing the edges are allowed to intersect. However, any representation of a $d$-dimensional rectangle $k$-visibility graph where the edges intersect can be transformed into a representation where the edges do not intersect by perturbing the edges slightly.

In the original version of bar/rectangle $k$-visibility graphs, the bars/rectangles are defined to be disjoint. However, it seems interesting to also consider what happens when they can intersect. In the case of bar visibility graphs with $n$ vertices where the bars can intersect, what is the maximum possible number of edges?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#7 • 1 Y
Y by Adventure10
goodbear wrote:
JGeneson wrote:
Does anyone see how to get any lower bounds for the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices?

Also, what are upper and lower bounds for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?

One obvious lower bound for $n>k$ is $n(k+1)-\frac{(k+1)(k+2)}2,$ which comes from putting $d$-dimensional cubes in a row, like so:

Diagram
What is the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?
Does anyone see a way to prove that the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#8 • 1 Y
Y by Adventure10
JGeneson wrote:
Does anyone see a way to prove that the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

Consider a bar $k$-visibility graph with $n$ vertices, with the maximum possible number of edges. Here is an example with $n=6,~k=1.$
[asy]
draw((0, 25)--(55, 25));
draw((10, 20)--(30, 20));
draw((15, 15)--(35, 15));
draw((25, 10)--(45, 10));
draw((20, 5)--(40, 5));
draw((5, 0)--(50, 0));

draw((8, 25)--(8, 0), dashed);
draw((12, 25)--(12, 20), dashed);
draw((13, 20)--(13, 0), dashed);
draw((17, 20)--(17, 15), dashed);
draw((18, 15)--(18, 0), dashed);
draw((22, 20)--(22, 5), dashed);
draw((23, 15)--(23, 5), dashed);
draw((27, 15)--(27, 10), dashed);
draw((28, 20)--(28, 10), dashed);
draw((32, 10)--(32, 5), dashed);
draw((33, 25)--(33, 15), dashed);
draw((37, 5)--(37, 0), dashed);
draw((38, 25)--(38, 5), dashed);
draw((42, 10)--(42, 0), dashed);
draw((43, 25)--(43, 10), dashed);
[/asy]

Consider the "$d$-dimensional analog" of this, shown below, again with $n=6,~k=1.$ Since this is a legitimate $d$-dimensional rectangle $k$-visibility graph with $n$ vertices, the maximum number of edges in such a graph is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices.
[asy]
import three;
currentprojection=perspective(-1/3,-1/5,1/6);

draw(shift((0,0,25))*(xscale3(55)*unitcube),rgb(0.6,1,0.7));
draw(shift((10,0,20))*(xscale3(20)*unitcube),rgb(0.6,1,0.7));
draw(shift((15,0,15))*(xscale3(20)*unitcube),rgb(0.6,1,0.7));
draw(shift((25,0,10))*(xscale3(20)*unitcube),rgb(0.6,1,0.7));
draw(shift((20,0,5))*(xscale3(20)*unitcube),rgb(0.6,1,0.7));
draw(shift((5,0,0))*(xscale3(45)*unitcube),rgb(0.6,1,0.7));

draw((8, 0, 25)--(8, 0, 0), dashed);
draw((12, 0, 25)--(12, 0, 20), dashed);
draw((13, 0, 20)--(13, 0, 0), dashed);
draw((17, 0, 20)--(17, 0, 15), dashed);
draw((18, 0, 15)--(18, 0, 0), dashed);
draw((22, 0, 20)--(22, 0, 5), dashed);
draw((23, 0, 15)--(23, 0, 5), dashed);
draw((27, 0, 15)--(27, 0, 10), dashed);
draw((28, 0, 20)--(28, 0, 10), dashed);
draw((32, 0, 10)--(32, 0, 5), dashed);
draw((33, 0, 25)--(33, 0, 15), dashed);
draw((37, 0, 5)--(37, 0, 0), dashed);
draw((38, 0, 25)--(38, 0, 5), dashed);
draw((42, 0, 10)--(42, 0, 0), dashed);
draw((43, 0, 25)--(43, 0, 10), dashed);
[/asy]
This post has been edited 5 times. Last edited by goodbear, Feb 5, 2017, 12:41 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#10 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
What is the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

In the Hartke paper, in Theorem 1, the authors prove that the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is at most $(k+1)(3n-4k-6)$ for $n\ge2k+2.$ (I don't know if this is achievable.) Otherwise, the construction like so gives $\binom n2,$ as all edges can see each other.

[asy]
for (int i=0; i<6; ++i) {
draw((-i-0.5,i)--(i+0.5,i));
}
for (int i=1; i<6; ++i) {
draw((-i-0.5,-i)--(i+0.5,-i));
}
[/asy]
This post has been edited 3 times. Last edited by goodbear, Feb 5, 2017, 1:07 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#11 • 2 Y
Y by Adventure10, Mango247
goodbear wrote:
JGeneson wrote:
What is the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

In the Hartke paper, in Theorem 1, the authors prove that the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is at most $(k+1)(3n-4k-6)$ for $n\ge2k+2.$ (I don't know if this is achievable.)

Theorem 7 of this paper proves that this bound is achievable:
http://jgaa.info/accepted/2007/Dean+2007.11.1.pdf
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#12 • 1 Y
Y by Adventure10
JGeneson wrote:
goodbear wrote:
JGeneson wrote:
What is the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

In the Hartke paper, in Theorem 1, the authors prove that the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is at most $(k+1)(3n-4k-6)$ for $n\ge2k+2.$ (I don't know if this is achievable.)

Theorem 7 of this paper proves that this bound is achievable:
http://jgaa.info/accepted/2007/Dean+2007.11.1.pdf

Okay, then the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.

Therefore, we can improve the lower bound in post #5, because by post #8, the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices, so the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.
This post has been edited 1 time. Last edited by goodbear, Feb 6, 2017, 6:08 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#13 • 2 Y
Y by Adventure10, Mango247
goodbear wrote:
JGeneson wrote:
goodbear wrote:
In the Hartke paper, in Theorem 1, the authors prove that the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is at most $(k+1)(3n-4k-6)$ for $n\ge2k+2.$ (I don't know if this is achievable.)

Theorem 7 of this paper proves that this bound is achievable:
http://jgaa.info/accepted/2007/Dean+2007.11.1.pdf

Okay, then the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.

Therefore, we can improve the lower bound in post #5, because by post #8, the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices, so the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.
Anyone see how to get an upper bound for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#14 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
goodbear wrote:
JGeneson wrote:
Theorem 7 of this paper proves that this bound is achievable:
http://jgaa.info/accepted/2007/Dean+2007.11.1.pdf

Okay, then the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.

Therefore, we can improve the lower bound in post #5, because by post #8, the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices, so the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.
Anyone see how to get an upper bound for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?

Would $d!\cdot(k+1)(3n-4k-6)$ be one such bound? In the Hartke paper, in the proof of Theorem 1, they prove this bound for $d=1,$ by induction for higher $d,$ we get this bound.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#15 • 2 Y
Y by Adventure10, Mango247
goodbear wrote:
JGeneson wrote:
goodbear wrote:
Okay, then the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices is $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.

Therefore, we can improve the lower bound in post #5, because by post #8, the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices, so the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices is at least $(k+1)(3n-4k-6)$ for $n\ge2k+2$ and $\binom n2$ otherwise.
Anyone see how to get an upper bound for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?

Would $d!\cdot(k+1)(3n-4k-6)$ be one such bound? In the Hartke paper, in the proof of Theorem 1, they prove this bound for $d=1,$ by induction for higher $d,$ we get this bound.
I was wrong before, we don't know yet whether this upper bound is right.
This post has been edited 1 time. Last edited by JGeneson, Mar 20, 2017, 9:03 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#16 • 1 Y
Y by Adventure10
JGeneson wrote:
goodbear wrote:
JGeneson wrote:
Anyone see how to get an upper bound for the maximum possible number of edges in a $d$-dimensional rectangle $k$-visibility graph with $n$ vertices?

Would $d!\cdot(k+1)(3n-4k-6)$ be one such bound? In the Hartke paper, in the proof of Theorem 1, they prove this bound for $d=1,$ by induction for higher $d,$ we get this bound.
This upper bound is right, but I think it can be sharpened. Is it possible to get an upper bound of $d(k+1)(3n-4k-6)$?

Can you give me a hint? I don't quite see it...
Z K Y
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Maximum number of edges in a rectangle k-visibility graph
JGeneson   90
N Oct 6, 2017 by goodbear
Is the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices at most twice the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

Why or why not?
90 replies
JGeneson
Dec 28, 2016
goodbear
Oct 6, 2017
J
No more topics!
H
J
H
Maximum number of edges in a rectangle k-visibility graph
JGeneson   90
N Oct 6, 2017 by goodbear
Is the maximum possible number of edges in a rectangle $k$-visibility graph with $n$ vertices at most twice the maximum possible number of edges in a bar $k$-visibility graph with $n$ vertices?

Why or why not?
90 replies
JGeneson
Dec 28, 2016
goodbear
Oct 6, 2017
J