SS24_VG: Question to 3.3

Hello to everyone,

We have a question for task 3. We are unsure, if the indices of the alogrithm are correct. We noticed a problem, when we walk through the algorithm with an example:

We have drawn the graph for k=3, and want to add v4. We know that w1=v1, w2=v3, w3=v2, since they are on the outer face of G3.

Now the first sentence in step 3 tells us that the neighbours of v5 in G4 are ordered by their order in the outer bound on G3. But v4 is a neighbour of v5 in G4 (and hence one of the points wp,...wq) but we don't know its order as it is not in G3.

Therefore we do not know the order of the neighbours of v5 and hence cannot detemine the x value of v4 in the next step because we don't know what wp and wq are and therefore don't know their x-coordinates.

Hopefully you can help us!

Re: Question to 3.3

от Oksana Firman - понедельник, 6 мая 2024, 13:19

Hello Sonja,

the graph G_k is a subgraph of G induced by the vertices v_1,...,v_k, i.e., G_k contains exactly the vertices v_1,...,v_k and the edges between these vertices (if they are in G). Thus, G_4 does not contain v_5. To draw G_4 you need to follow step 3 and place the vertex v_4 according to the rule. Then, to draw G_5, you already have the drawing of G_4 (the coordinates of the vertices v_1,v_2,v_3,v_4). Thus, you know in which order the neighbours of v_5 that are in G_4 appears on the outer face.
I hope this helps in understanding step 3. If something is still unclear or if you have any further questions, let me know.

Best wishes,
Oksana

Re: Question to 3.3

от Sonja Hatzenbühler - понедельник, 6 мая 2024, 14:38

Thanks,
but we still do not quite understand how it works. I attached the example graph G we tried to use the algorithm for.

The problem appears when we're trying to add v4 and follow the instructions given in step 3:

Assume G_{k-1}=G3 since we now want to add v4 and hence k=4. Then we consider the vertices w1, ..., wp,...,wq,...wq on the boundary of the outer face of G3, which are v1, v3, v2 (in this order). But the next part of the sentence tells us that wp,...,wq are the neighbours of v_{k+1}=v5 in G_{k}=G4. Now that would also include v4 which is a neighbour of v5 in G4. But that poses the problem of not knowing which points are to be considered in wp,...,wq and how they are ordered. Could it be that instead of wp,...,wq being the neighbours of v_{k+1} in Gk, wp,...,wq are the neighbours of vk in Gk? In this case we see no problem in the application of the algorithm.

Re: Question to 3.3

от Oksana Firman - вторник, 7 мая 2024, 09:25

Dear Sonja,

I see and yes, you are right, there is a mistake in indices.
The correct sentence is "... where w_1 = v_1, w_t = v_2, and w_p, ..., w_q are the neighbors of v_k in G_{k-1}." It means that w_p, ..., w_q are the vertices of G_{k-1} and are the neighbors of v_k.

Thanks for pointing it! I have already uploaded the updated version without the mistake.

Best wishes,
Oksana