Opened 16 months ago

Closed 11 months ago

# Drawing generalizations of generalized Petersen graphs

Reported by: Owned by: gh-NinaKl gh-NinaKl major sage-9.3 graph theory gh-vipul79321 Nina Klobas David Coudert N/A 0d739ba

### comment:1 Changed 16 months ago by gh-NinaKl

• Branch set to u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs

### comment:2 Changed 16 months ago by gh-NinaKl

• Authors set to Nina Klobas
• Commit set to 7f3ef45d91838eccdc0e97a524800df92b7afb79
• Component changed from PLEASE CHANGE to graph theory
• Type changed from PLEASE CHANGE to enhancement

New commits:

 ​7f3ef45 Added nice drawings for 4 graph families

### comment:3 Changed 16 months ago by gh-NinaKl

• Owner changed from (none) to gh-NinaKl

### comment:4 Changed 16 months ago by gh-NinaKl

• Status changed from new to needs_review

### comment:5 Changed 16 months ago by dcoudert

• Reviewers set to David Coudert
• Status changed from needs_review to needs_work

Hello,

Thank you for contributing new graphs with nice embeddings.

Several improvements are needed in your code (which contains errors). I'm putting below a nicer and corrected version of method IGraph. Use it to improve the code of the other methods.

def IGraph(n, j, k):
r"""
Return an I-graph with 2n nodes.

The variables n, j, k are integers such that n > 2 and
0 < j, k \leq \lfloor (n - 1) / 2 \rfloor.
When j = 1 the resulting graph is isomorphic to the generalized Petersen
graph with the same n and k.

INPUT:

- n -- the number of nodes is 2 * n

- j -- integer 0 < j \leq \lfloor (n-1)/2 \rfloor. Decides how outer
vertices are connected.

- k -- integer 0 < k \leq \lfloor (n-1)/2 \rfloor. Decides how inner
vertices are connected.

PLOTTING: Upon construction, the position dictionary is filled to override
the spring-layout algorithm. By convention, the I-graphs are displayed as an
inner and outer cycle pair, with the first n nodes drawn on the outer
circle.  The first (0) node is drawn at the top of the outer-circle, moving
counterclockwise after that. The inner circle is drawn with the (n)th node
at the top, then counterclockwise as well.

EXAMPLES:

When j = 1 the resulting graph will be isomorphic to a generalized
Petersen graph::

sage: g = graphs.IGraph(7,1,2)
sage: g2 = GeneralizedPetersenGraph(7,2)
sage: g.is_isomorphic(g2)
True
"""
if n < 3:
raise ValueError("n must be larger than 2")
if j < 1 or j > (n - 1) // 2:
raise ValueError("j must be in 1 <= j <= floor((n - 1) / 2)")
if k < 1 or k > (n - 1) // 2:
raise ValueError("k must be in 1 <= k <= floor((n - 1) / 2)")

G = Graph(2 * n, name="I-graph (n={}, j={}, k={})".format(n, j, k))
for i in range(n):
G.add_edge(i, (i + j) % n)
G.add_edge(i + n, n + (i + k) % n)
return G


Could you also explain what is a IGraph ? For me this name is confusing since there is a graph library called igraph. Is it the most appropriate name ?

### comment:6 Changed 16 months ago by git

• Commit changed from 7f3ef45d91838eccdc0e97a524800df92b7afb79 to d5b51a0369da31db3078e5b5352eda52f1f581c9

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d5b51a0 Better structure of code

### comment:7 Changed 16 months ago by gh-NinaKl

Regarding the definition of I-graphs one could check page 2 of the following paper.

### comment:8 Changed 16 months ago by dcoudert

You should add references to the definitions of these graphs. See e.g., #11736 for examples.

Also add a EXAMPLES: block to all methods.

### comment:10 Changed 15 months ago by mkoeppe

• Milestone changed from sage-9.2 to sage-9.3

### comment:11 Changed 13 months ago by dcoudert

• Branch changed from u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs to public/graphs/30728_drawings
• Commit changed from d5b51a0369da31db3078e5b5352eda52f1f581c9 to a2948cdcda637ba5a43646d53ba99afcb032fe44
• Status changed from needs_work to needs_review

I have rebased the branch on sage 9.3.beta5 performed several corrections / improvements. In particular, I have added missing references and updated some definitions to fit the original papers.

New commits:

 ​f60310c trac #30728: merge with 9.3.beta5 ​a2948cd trac #30728: review commit

### comment:12 Changed 13 months ago by git

• Commit changed from a2948cdcda637ba5a43646d53ba99afcb032fe44 to 0d739ba082b679d266731e50e3709dbef5b1ee10

Branch pushed to git repo; I updated commit sha1. New commits:

 ​0d739ba trac #30728: fix block issue

### comment:13 Changed 13 months ago by dcoudert

For me this patch is now good to go, but a double check would be appreciated.

### comment:14 Changed 12 months ago by dcoudert

• Status changed from needs_review to positive_review

I give this ticket a positive review. I did review edit to fix some issues and we have green bot since several weeks.

### comment:15 Changed 11 months ago by vbraun

• Branch changed from public/graphs/30728_drawings to 0d739ba082b679d266731e50e3709dbef5b1ee10
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:16 Changed 11 months ago by slelievre

• Commit 0d739ba082b679d266731e50e3709dbef5b1ee10 deleted

Some "TESTS" blocks have a single colon : instead of double colon ::.

Please fix in follow-up ticket #31461.

Note: See TracTickets for help on using tickets.